How to prove or disprove $n^{28} = O(2^n)$

Question

Prove or disprove $n^{28} = O(2^n)$.

My solution: $$\lim _{n \to \infty} \dfrac {2^n} {n^{28}} = \dfrac {2*2*2 \dots _{(n \ times)}} {n * n * \dots _{(28 \ times)}}$$ As $n \to \infty$, both the numerator and the denominator approach $\infty$.
So am not sure whether $2^n = O(n^{28})$ or the other way around.

Answer 1

Apply l'Hopital's rule 28 times and we have

$$\lim_{n\to\infty} \frac{n^{28}}{2^n} = \lim_{n\to\infty} \frac{28!}{(\ln 2)^{28} 2^n} = 0$$

Thus there exists a constant $M$ such that for sufficiently large $n$, we have $$n^{28} \leq M 2^n$$

Choosing $M = 1$ will do. Hence by definition of the big O notation, $n^{28} = O(2^n)$.

It is however not true that $2^n = O(n^{28})$, as $\displaystyle \frac{2^n} {n^{28}}$ can be made arbitrarily large by choosing a sufficiently large $n$. That is, there is no constant $M$ such that for all sufficiently large $n$ we have

$$2^n \leq M n^{28}$$

Answer 2

Since $log(n) = o(n)$ as $n \to \infty$, we have $$ \frac{n^{28}}{2^{n}} = \frac{\exp (28 \log n)}{\exp (n \log 2)} \to 0 $$ as $n \to \infty$, i.e. $n^{28} = o(2^{n})$, so $n^{28} = O(2^{n})$.

Answer 3

In this simple example you are supposed to show that there exist $M \ge 0$ such that $\lim \limits _{n \to \infty} \frac {n^{28}} {2^n} = M$ (in more complicated examples you would have to use $\varlimsup$, but let us not complicate the discussion). Let us show that $M=0$.

It is easier and equivalent to compute $\lim \limits _{n \to \infty} \frac n {\sqrt[28]2^n}$ and then raise the result to the power $28$. Instead, let us do something more general: show that $\lim \limits _{n \to \infty} \frac n {q^n} = 0$ whenever $q>1$ (to solve your specific problem take $q = \sqrt[28] 2$).

There are two essentially equivalent approaches: you could promote your sequences to (derivable) functions of a real positive variable and apply L'Hospital's theorem: $\lim \limits _{x \to \infty} \frac x {q^x} = \lim \limits _{x \to \infty} \frac 1 {q^x \ln q} = 0$. The other approach is to use the Stolz-Cesàro theorem: $\lim \limits _{n \to \infty} \frac n {q^n} = \lim \limits _{n \to \infty} \frac {n+1 - n} {q^{n+1} - q^n} = \lim \limits _{n \to \infty} \frac 1 {q^n (q-1)} = 0$.