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.

  • $\begingroup$ 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$. $\endgroup$
    – 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$.

What is done in CLRS is a shortened version of above transformations.

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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.