# Polylogarithm growth rate proof using Polynomial growth equation

In the CLRS, there's this part, where it's shown that $$\lim_{n\to\infty}\frac{(n^b)}{(a^n)} = 0$$ In the same chapter, it uses the aforementioned equation to prove that any polylogarithm function grows slower than any polynomial one, thus, $$\lim_{n\to\infty}\frac{\log b^n}{ n^a}$$ It does that by substituting lgn for n and 2^a for a in the first equation. How is it allowed to substitute the terms and prove the latter equation.

• There is typo in the last formula. $\log b^n$ should be $\log^n b$. The former means $\log (b^n)$, which is equal to $n\log b$, a linear function of variable $n$ while the later means $(\log n)^b$, a polylogarithm function of variable $n$. – John L. Feb 3 '19 at 16:36

Here is the starting point. For all real constants $$a$$ and $$b$$ such that $$a > 1$$, $$\lim_{n\to\infty}\frac{n^b}{a^n} = 0\,.\tag{3.10}$$
Let $$c=\log_2 a$$, i.e, $$a=2^c$$. Since $$a>1$$, we have $$c>0$$. Equation (3.10) becomes $$\lim_{n\to\infty}\frac{n^b}{a^n} = \lim_{n\to\infty}\frac{n^b}{2^{cn}}= 0\,.\tag{cs.1}$$
Let $$m=2^n$$, i.e, $$n=\log_2 m$$. Then equation (cs.1) becomes $$\lim_{n\to\infty}\frac{n^b}{2^{cn}} = \lim_{m\to\infty}\frac{(\log_2 m)^b}{2^{c\log_2 m}} = \lim_{m\to\infty}\frac{(\log_2m)^b}{m^{c}}= 0\,.\tag{cs.2}$$
Note that equation (cs.2) is, after $$m$$ is renamed to $$n$$ and $$c$$ is renamed to $$a$$, $$\lim_{n\to\infty}\frac{(\log_2 n)^b}{ n^a}=\lim_{n\to\infty}\frac{{\lg}^b n}{ n^a}=0\tag{cs.3}$$ where $$a>0$$.
Be careful. $$(\log_2n)^b={\lg}^bn\not=\log_2n^b=\log_2(n^b)$$, where each of two equalities is just a change of notation. $$\log_2 (b^n)$$, which is equal to $$n\log_2 b$$, is a linear function of variable $$n$$ while $$(\log_2 n)^b$$ is a polylogarithm function of variable $$n$$.