2.21

Let [math]f(n)=a_k n^k+a_{k-1}n^{k-1}+\dots +a_1 n+a_0[/math] with [math]k\ge 1[/math] and constants [math]a_0,\dots ,a_k\in\mathbb R[/math].

Definition: [math]f(n)=O(n^k)[/math] means ∃ positive constants [math]C[/math] and [math]N[/math] such that
[math]\displaystyle |f(n)|\le C\,n^k\qquad\forall\,n\ge N.[/math]

Proof:
1. For every term with exponent [math]i\le k[/math] and for every [math]n\ge 1[/math] we have [math]n^{\,i}\le n^{\,k}[/math].
2. Hence
[math]\displaystyle |f(n)|\le |a_k|n^k+|a_{k-1}|n^{k-1}+\dots+|a_0| \le \bigl(|a_k|+|a_{k-1}|+\dots+|a_0|\bigr)n^k.[/math]
3. Let
[math]\displaystyle C:=|a_k|+|a_{k-1}|+\dots+|a_0|\quad\text{and}\quad N:=1.[/math]
Then for all [math]n\ge N[/math] the inequality in step 2 gives [math]|f(n)|\le C n^k[/math].

Thus, by definition, [math]f(n)=O(n^k)[/math].✅

Back to Chapter 2