patternMinor
Polylogarithm growth rate proof using Polynomial growth equation
Viewed 0 times
polynomialratepolylogarithmusinggrowthequationproof
Problem
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.Solution
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$.
$$\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$.
Context
StackExchange Computer Science Q#103744, answer score: 3
Revisions (0)
No revisions yet.