Prove that $n^{55} = O(2^n)$

97 Views Asked by At

How can I prove that $n^{55} = O(2^n)$ using the following Big O definition: $$ f(g(n)) = O(g(n)) \\ \Leftrightarrow $$ there are positive constants $c$ and $n_0$, such that $|f(g(n))| \le c \cdot g(n)$, for all $n \ge n_0$.

I know that $n^c$ will always grow slower than $2^n.$

So we start with: $$ 10n^{55} \le c \cdot 2^n. $$

Then, I used logarithms but without success :(

I also thought of some how turn the exponential function into a polynomial one, or vice versa, but as a computer science student, I have no idea how to do that.

1

There are 1 best solutions below

0
On

Hint:

$$\left(1+\frac1{79}\right)^{55}<2$$

so that for all $n\ge79$,

$$\left(\frac{n+1}n\right)^{55}<2$$

and by the telescoping product, $n^{55}$ grows slower than $2^n$.