Proofs of Algorithm Correctness and Runtime Estimates · Function Growth Rates

Lesson 3

Nikolai Chukhin · Alexander S. Kulikov

Consider two functions \(f, g \colon \mathbb{Z}_{>0}\to \mathbb{R}_{>0}\) (\(f\) and \(g\) take positive integers as inputs and yield positive real numbers). We say that \(f\) grows no faster than \(g\) and write \(f(n) \preceq g(n)\) if there exists a constant \(\alpha>0\) such that for all positive integers \(n\) the inequality \[f(n) \le \alpha \cdot g(n) \ .\] holds.

Returning to the example from the previous step, let's show that \(2n^{2}+5n+3\) grows no faster than \(n^{2}\). Indeed, for all positive integers \(n\) the inequalities \(1 \le n\) and \(n \le n^{2}\) hold, therefore \[2n^{2}+5n+3 \le 2n^{2}+5n^{2}+3n^{2}=10n^{2}.\] Thus, we can take \(\alpha=10\).

For the curious 🤓
In the literature, you can find a more general definition: it is said that \(f(n) \preceq g(n)\) if there exist such \(N\) and \(\alpha\) that for all \(n \ge N\) the inequality \(f(n) \le \alpha \cdot g(n)\) holds. For functions \(f, g \colon \mathbb{Z}_{>0}\to \mathbb{R}_{>0}\) (i.e., defined on positive integers and having positive values) these two definitions are equivalent. Indeed, if \(f(n) \le \alpha g(n)\) for all \(n \ge N\), take \[\gamma=\max\left(\{\alpha\}\cup\left\{\frac{f(n)}{g(n)}\colon 1 \le n < N \right\}\right).\] This maximum is defined even when \(N=1\), because the set still contains \(\alpha\). Let's now show that \(f(n) \le \gamma g(n)\) for all positive integers \(n\). For this, consider two cases.
  1. \(n < N\). Then \(\frac{f(n)}{g(n)}\le \gamma\), i.e., \(f(n) \le \gamma \cdot g(n)\).
  2. \(n \ge N\). Then \(f(n) \le \alpha g(n) \le \gamma \cdot g(n)\).