Using big-O to prove N^2 is O(2^N)

Question

I can clearly see than N^2 is bounded by c2^N, but how do i prove it by using formal definition of big-O. I can simply prove it by M.I.

Here is my attempt.. By definition, there for any n>n0, there exist a constant C which f(n) <= Cg(n) where f(n) = n^2 and g(n) = 2^n

Should I take log to both side and solve for C?

and one more question about fibonacci sequence, i wanna solve the recurrence relation.

int fib(int n){
   if(n<=1) return n;
   else return fib(n-1) + fib(n-2);

The equation is..

T(n) = T(n-1)+T(n-2)+C // where c is for the adding operation

so

T(n) = T(n-2) + 2T(n-3) + T(n-4) + 3c 

and one more

T(n) = T(n-3) + 3T(n-4) + 3T(n-5) + T(n-6) + 6c

then i started to get lost to form the general equation i The pattern is somehow like pascal triangle?

 t(n) = t(n-i) + aT(n-i-1) + bT(n-i-2) + ... + kT(n-i-i) + C 

Answer 1

As you point out, to see if f(x) ϵ O(g(x)) you need to find...

• ...some c > 0 and
• ...some x₀

such that f(x) < c·g(x) for all x > x₀.

In this case, you can pick c = 1 and x₀ = 2. What you need to prove is that

    x² < 2^x for all x > 2

At this point you can log both sides (since if log(x) > log(y), then x > y.) Assuming you're using base-2 log you get the following

    log(x²) < log(2^x)

and by standard laws of logarithms, you get

    2·log(x) < x·log(2)

Since log(2) = 1 this can be written as

    2·log(x) < x

If we set x = 2, we get

    2·log(2) = 2

and since x grows faster than log(x) we know that 2·log(x) < x holds for all x > 2.

Answer 2

For the most part, the accepted answer (from aioobe) is correct, but there is an important correction that needs to be made.

Yes, for x=2, 2×log(x) = x or 2×log(2) = 2 is correct, but then he incorrectly implies that 2×log(x) < x is true for ALL x>2, which is not true.

Let's take x=3, so the equation becomes: 2×log(3) < 3 (an invalid equation).

If you calculate this, you get: 2×log(3) ≈ 3,16993 which is greater than 3.

You can clearly see this if you plot f(x) = x² and g(x) = 2^x or if you plot f(x)= 2×log(x) and g(x) = x (if c=1).

Between x=2 and x=4, you can see that g(x) will dip below f(x). It is only when x ≥ 4, that f(x) will remain ≤ c×g(x).

So to get the correct answer, you follow the steps described in aioobe's answer, but you plot the functions to get the last intersection where f(x) = c×g(x). The x at that intersection is your x₀ (together with the choosen c) for which the following is true: f(x) ≤ c×g(x) for all x ≥ x₀.

So for c=1 it should be: for all x≥4, or x₀=4