In the CLRS book, 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 logarithmic 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.
No comments:
Post a Comment