Lesson 5

We are ready to prove one of the most important properties about the growth rate of functions. Theorem. Any polynomial function grows slower than any exponential function: for any \(k>0\) and \(c>1\), \[n^{k} \prec c^{n} \ .\]

Before proving this theorem, note that we have already proved something similar when discussing the method of mathematical induction. Specifically, one can prove by induction that \(n^{2} \le 2^{n}\) for all integers \(n \ge 4\). Indeed, at \(n=4\) (base of induction) the inequality holds: \(4^{2}=16=2^{4}\). With each increment of \(n\) by one (inductive step), the value of the exponential function \(2^{n}\) doubles, whereas the value of the polynomial is multiplied by \[\frac{(n+1)^2}{n^2}=\left(\frac{n+1}{n}\right)^{2}=\left(1+\frac{1}{n}\right)^{2}.\] As \(n\) grows, this number becomes smaller and smaller. For \(n \ge 4\), this number is no more than \((1+1/4)^{2}=1.5625\).

This effect can be seen on the graph. At \(n=4\), the two graphs meet, after which the exponent \(2^{n}\) moves further and further away from the polynomial \(n^{2}\) (because, as we found out, with each increment of \(n\) by one, the exponent multiplies by two, whereas the polynomial is multiplied by a number that is not only always less than two but also itself becomes smaller).

import matplotlib.pyplot as plt
import numpy as np

n = np.linspace(1, 8)
plt.plot(n, n ** 2, label='$n^2$')
plt.plot(n,  2 ** n, label='$2^n$')
plt.legend()
plt.savefig('poly_exp.png')

From the fact that \(n^{2} \le 2^{n}\) for all \(n \ge 4\), we conclude that \(n^{2}\) grows no faster than \(2^{n}\) (i.e., \(n^{2} \preceq 2^{n}\)): it is easy to see that \(n^{2} \le 2 \cdot 2^{n}\) for all positive integers \(n\). In fact, a stronger statement is true: \(n^{2}\) grows slower than \(2^{n}\) (i.e., \(n^{2} \prec 2^{n}\)). Intuitively, this is understandable from the reasoning above: \(2^{n}\) moves further away from \(n^{2}\), so there cannot be a constant \(\alpha\) for which the inequality \(2^{n} \le \alpha n^{2}\) would hold for all \(n\). We will formally prove this below.

Proof. First, let's show that \(n^{k}\) grows no faster than \(c^{n}\): \[n^{k} \preceq c^{n}.\] To do this, let's show that at some point \(c^{n}\) will overtake \(n^{k}\): there exists \(N\), such that \(n^{k} \le c^{n}\) for all \(n > N\). This will be enough, because for \(n \le N\) the inequality \(n^{k} \le \alpha c^{n}\) holds, where \[\alpha=\max\left\{\frac{n^k}{c^n}\colon 1 \le n \le N\right\}.\] Rewrite the inequality \(n^{k} \le c^{n}\) as: \[n^{k} \le 2^{n \cdot \log_2 c}.\] Raise it to the power of \(\frac{1}{k}\): \[n \le 2^{n \cdot \frac{\log_2 c}{k}}.\] Let now \(m=n \cdot \frac{\log_2 c}{k}\). That is, the parameters \(m\) and \(n\) differ from each other by a constant factor \(\frac{\log_2 c}{k}\). In terms of the new parameter \(m\), the last inequality rewrites as: \[m \cdot \frac{k}{\log_2 c}\le 2^{m} \ .\] Set \(C=\frac{k}{\log_2c}\) and \(t=\lfloor m\rfloor\). If \(t\ge4\) and \(t\ge2C\), then \(m<t+1\le2t\), and therefore \[mC\le2tC\le t^{2}\le2^{t}\le2^{m}.\] These conditions hold for all sufficiently large \(n\).

Now let's show that \(n^{k}\) grows slower than \(c^{n}\): \[n^{k} \prec c^{n}.\] To do this, let's show that it is not true that \(c^{n}\) grows no faster than \(n^{k}\). Suppose that it is indeed so: there exists a constant \(\alpha>0\) such that \(c^{n} \le \alpha n^{k}\). Since \(c>1\), there will be a number \(b\), such that \(c>b>1\) (for example, the number \(b=\frac{c+1}{2}\), i.e., the midpoint of the interval \([1,c]\) will do). As we already know, \(n^{k}\) grows no faster than \(b^{n}\): there exists a number \(\beta>0\), such that \(n^{k} \le \beta b^{n}\) for all \(n\). Combining the two inequalities, we get that for all \(n\) it holds that \[c^{n} \le \alpha n^{k} \le \alpha \beta b^{n} .\] But then \[\left(\frac{c}{b}\right)^{n} \le \alpha \beta\] for all \(n\), which is not true, because \(\frac{c}{b}>1\), and thus, the function \((c/b)^{n}\) grows indefinitely.◼