Lesson 7

The theorem just proven allows us to conclude that the logarithmic function (and even any power of it) grows slower than any polynomial function.

First, let's show that for constants \(a,b>1\), the functions \(\log_{a}{n}\) and \(\log_{b}{n}\) have the same order of growth. Indeed, by the base change formula for logarithms, these two functions differ from each other by a constant multiplier: \[\frac{\log_{a}{n}}{\log_{b}{n}}=\frac{\frac{\log_{2}{n}}{\log_{2}{a}}}{\frac{\log_{2}{n}}{\log_{2}{b}}}=\frac{\log_{2}{b}}{\log_{2}{a}}.\] For this reason, often in asymptotic estimates, the base of the logarithm is not specified at all, and you might encounter statements like: “The runtime of this sorting algorithm grows as \(n\log{n}\)”.

Now, let's show that for any \(a>0\), \(b>1\), and \(k>1\), the function \((\log_{b}{n})^{a}\) (called a polylogarithmic function) grows slower than the power function \(n^{k}\): \[(\log_{b}{n})^{a} \prec n^{k} \ .\] Indeed, let \(m=\log_{b}{n}\). The parameter \(m\) increases with \(n\). Then \((\log_{b}{n})^{a}=m^{a}\), that is, in terms of \(m\) it is simply a power function. And the function \(n^{k}\) is exponential in terms of \(m\): \[n^{k}=\left(b^{\log_{b}{n}}\right)^{k}=\left(b^{m}\right)^{k}=b^{mk}=\left(b^{k}\right)^{m} .\] As we already know, the function \(m^{a}\) grows slower than the function \((b^{k})^{m}\).