Lesson 4

Just as in the example above, one can show for any polynomial that it grows no faster than its leading monomial. For example, \[3n^{3}+2n^{2}+7n+10 \preceq n^{3} \ .\] Note, by the way, that \(n^{3}\) also grows no faster than \(3n^{3}+2n^{2}+7n+10\), and this is immediate (as \(\alpha\) one can simply take one). When for two functions \(f(n)\) and \(g(n)\) it holds that each of them grows no faster than the other, it is said that these two functions grow at the same rate or have the same order of growth. This is denoted as: \(f(n) \asymp g(n)\).

Let's compare the growth rates of the power functions \(n^{l}\) and \(n^{k}\) for \(0 \le l < k\). Of course, \(n^{l} \le n^{k}\) for all positive integers \(n\), so \(n^{l}\) grows no faster than \(n^{k}\), i.e., \(n^{l} \preceq n^{k}\). But the reverse is not true: it is not true that \(n^{k}\) grows no faster than \(n^{l}\). Indeed, if there existed a constant \(\alpha>0\) such that \(n^{k} \le \alpha \cdot n^{l}\) for all positive integers \(n\), then after dividing by \(n^{l}\) we would get \[n^{k-l}\le \alpha.\] But \(k-l>0\), which means the function \(n^{k-l}\) grows indefinitely.

We say that \(f(n)\) grows slower than \(g(n)\), and write \(f(n) \prec g(n)\), if \(f(n)\) grows no faster than \(g(n)\) (i.e., \(f(n) \preceq g(n)\)), but it is not true that \(g(n)\) grows no faster than \(f(n)\) (i.e., \(g(n) \not \preceq f(n)\)).

From the reasoning above, we conclude that \[n \prec n^{1.5}\prec n^{2} \prec n^{3} \prec n^{4}.\]

Problem. Mark the correct statements: