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

Question

I clearly see that N ^ 2 is limited to c2 ^ N, but how to prove it using the formal definition of big-O. I can just prove it to M.I.

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

Should I take a magazine on both sides and decide for C?

and one more question about the fibonacci sequence, I want to solve the recurrence relation.

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

The equation...

 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(ni) + aT(ni-1) + bT(ni-2) + ... + kT(nii) + C 

Answer 1

As you point out, to see if f (x) ε O (g (x)) needs to be found ...

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

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

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

x ² 2 ^x for all x> 2

At this point, you can register both sides (since if log (x)> log (y), then x> y.) Assuming you are using back file 2, you get the following

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

and the standard laws of logarithms you get

2? log (x) <x & middot; log in (2)

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

2? log (x) <x

If we put x = 2, we get

2? log (2) = 2

and since x grows faster than log (x), we know that 2 & middot; log (x) x holds for all x> 2.

Answer 2

To improve the accepted answer:

You must prove that x ^ 2 <2 ^ x for all x> 2

Taking log from both sides, we must prove that: 2 * log (x) x for all x> 2

Thus, we must show the function h (x) = x-2 · log (x)> 0 for all x> 2

h (2) = 0

Differentiating h (x) with respect to x, we obtain h '(x) = 1 - 1 / (x · ln (2))

For all x> 2, h '(x) is always greater than 0; therefore, h (x) continues to increase, and since h (2) = 0, it is therefore proved that h (x)> 0 for all x> 2, or x ^ 2 <2 ^ x for all x> 2