Prove asymptotic bound?

Question

Prove: $$n^b = \mathcal{o}(a^n)$$

for and constants $b$ and $a$, where $a > 1$. The book states that:

$$\lim_{ n \rightarrow \infty} \frac{n^b}{a^n} = 0$$

The book doesn't prove the limit though. Thanks for the help.

Answer 1

That is one way to prove that exponential complexity ($a^n$) is always greater than polynomial complexity ($n^b$). Here is the formal definition of the statement $n^b$ is $o(a^n)$:

$$n^b \text{ is } o(a^n) \iff \{\forall c>0,n>n_0: |n^b| < c|a^n| \}$$ $$ \frac{n^b}{a^n} < c $$ $$ \frac{a^{b \log_a(n)}}{a^{n}}< c \quad (\text{Since }n=a^{\log_an})$$ $$ a^{b \log_a(n)-n} < c $$

This is expression is true since $\lim_{n \rightarrow \infty} a^{b \log_a(n)-n} = 0$.

$$\therefore n^b \text{ is } o(a^n)$$

The limit from the book should be: $$\lim_{n \rightarrow \infty} \frac{n^b}{a^n} = 0$$

which shows that $a^n$ dominates the expression $n^b$ (definition of little o). Hope this helps!

Answer 2

You are right. The correct statement should be $$ \lim_{n\to\infty}\frac{n^b}{a^n}=0 $$ for any constants $a,b$ and $a>1$. For $b\le 0$, it is trivial. For $b>0$, let $m$ be an integer such that $0\le m\le k<m+1$. Let $c=a-1>0$. Since, for $n>m+1$, $$ a^n=(1+c)^n=\sum_{k=0}\binom{n}{k}c^k\ge \binom{n}{m+1}c^{m+1} $$ we have $$0<\frac{n^b}{a^n}<\frac{n^b}{\binom{n}{m+1}c^{m+1}}. $$ It is easy to check $$\lim_{n\to\infty}\frac{n^b}{\binom{n}{m+1}}=0. $$ Thus $$ \lim_{n\to\infty}\frac{n^b}{a^n}=0. $$