Compare the growth of $2^{n}$ to $n^{a}$ for all $a \in \mathbb{N}$?

Question

How to find which of $2^{n}$ to $n^{a}$ is an (upper bound, tight bound asymptotically larger, etc..)? I tried to use the formula:

$$ \lim_{n\to\infty} \frac{f(n)}{g(n)} $$

where $f(n) = n^{a}$ and $f(n) = 2^{n}$

But I cannot figure out how to use L'Hospital's rule to solve it. We are guaranteed that $a \in \mathbb{N}$.

Answer 1

As a hint, $n^\alpha = 2^{\alpha \log_2 n}$. Now, you can compute the ratio between these functions by subtracting the exponents. There's no need to use l'Hôpital's rule.

Answer 2

Hint: $\frac{(n+1)^\alpha}{n^\alpha} \to 1$, so for any $C>1$ you can show that $n^\alpha = O(C^n)$. If you take $C < 2$ then you get that $n^\alpha = o(2^n)$.

Answer 3

If you want to use L'Hopital's rule to prove $n^{a}=o(2^n)$ that is fairly easy.

Lets consider the lemma in this question's accepted answer. The problem reduces to calculate the limit:

$$ \lim_{n\to\infty} \frac{n^a}{2^n} $$

This limit is of the type "infinite divided by infinite". So we can try to use L'Hopital's rule.

Let $f^i(n)$ be the ith derivative of $f(n)$ and $g^i(n)$ be the ith derivative of $g(n)$. Consider the following properties of $f(n)=n^a$ and $g(n)=2^n$:

$$f^i(n) = a(a-1)(a-2)...(a-i+2)(a-i+1)n^{a-i} $$ $$g^i(n) = 2^n*log^i(2)$$

As you can see the following LHopital's Rule's conditions comply:

• $f$ and $g$ are differentiable in the interval $]1,\infty[$.
• $g$ and $g'$ are nonzero in the interval $]1, \infty[$.
• As $n \rightarrow \infty$:

$$\frac{f(n)}{g(n)}\rightarrow \frac{\infty}{\infty}$$

This conditions also comply for the derivatives of $f$ and $g$.

Now we use L'Hopital's rule "a" times: We have to derive $f(n)$ and $g(n)$ "a" times and the result is:

$$ \lim_{n\to\infty} \frac{n^a}{2^n} = \lim_{n\to\infty} \frac{a(a-1)(a-2)...(2)(1)*n^0}{2^n*log^a(2)} \rightarrow \frac{a(a-1)(a-2)...(2)(1)*1}{2^\infty*log^a(2)}= 0 $$

Finally the last condition of L'Hopital rule complies:

• The limit exist(in this case is defined).

and the limit is zero as requested so $n^{a}=o(2^n)$.