Search code examples
asymptotic-complexityinequalitybig-o

Proving that a function f(n) belongs to a Big-Theta(g(n))

Its a exercise that ask to indicate the class Big-Theta(g(n)) the functions belongs to and to prove the assertion.

In this case f(n) = (n^2+1)^10

By definition f(n) E Big-Theta(g(n)) <=> c1*g(n) < f(n) < c2*g(n), where c1 and c2 are two constants.

I know that for this specific f(n) the Big-Theta is g(n^20) but I don't know who to prove it properly. I guess I need to manipulate this inequality but I don't know how

Solution

  • A function f(x) is Θ(g(x)), iff:

    • f(x) is O(g(x)), and
    • g(x) is O(f(x))

    So, while you could try to prove it in a single inequality, I suggest you break it down into those two parts; first prove that for some n>n0 f(n) < c1 g(n), and then prove that for some N > N0 g(N) < c2 f(N). Once you have proven both parts, separately, you can go back to the definition of Θ to prove that f = Θ(g).