Skip to main content
1 of 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)$$

So using L'Hopital's rule 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)} =\frac{a(a-1)(a-2)...(2)(1)*1}{2^\infty*log^a(2)}= 0 $$

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