Section 4.1 Big O Notation And Friends
Subsection 4.1.1 Big O Notation
It is equivalent to say that
\begin{equation*}
\limsup \frac{|f(x)|}{g(x)} \lt \infty\text{.}
\end{equation*}
Let us compare two closely related conditions:
- There exist \(M\) and \(x_0\) such that \(|f(x)| \leq M g(x)\) for all \(x \geq x_0\)
- There exists \(M'\) such that \(|f(x)| \leq M' g(x)\) for all \(x \geq a\)
Of course the second condition implies the first one (with \(x_0 = a\)). The first condition often implies the second one. If the ratio \(|f(x)|/g(x)\) is bounded on the interval \([a,x_0]\text{,}\) say by some value \(K\text{,}\) then we can set \(M'\) to be the maximum of \(M\) and \(K\text{.}\) The only way this ratio can fail to be bounded is if \(|f(x)|\) approaches \(\infty\) or \(g\) approaches \(0\text{.}\) If \(f\) is bounded and \(g\) is bounded away from zero (bounded below) then the ratio \(f/g\) is bounded. This will be the case if both \(f\) and \(g\) are continuous. (Exercise: if \(g\) is continuous and \(g(x) \gt 0\) for all \(x\text{,}\) then there exists \(\epsilon \gt 0\) such that \(g(x) \geq \epsilon\) for all \(x\text{.}\)) Therefore, the two conditions above are equivalent for continuous \(f\) and \(g\) (or, with suitable boundedness assumptions instead of continuity). In those cases we can ignore the issue of “eventuality”. Of course, the values \(M\) and \(M'\) may be different.
Sometimes the notation \(O(g(x))\) represents an unspecified function \(f\) that is \(O(g)\) in the sense defined above.
Example 4.1.2.
-
Any polynomial of degree \(d\) is \(O(x^d)\text{.}\)Indeed, let \(C\) be the largest absolute value of a coefficient of any term in the polynomial; for \(x \gt 1\) the polynomial is bounded by \(C(d+1)x^d\) since there are at most \(d+1\) terms, each bounded by \(Cx^d\text{.}\)
- \(x^a = O(x^b)\) if and only if \(a \leq b\) (here we allow \(a, b \leq 0\)). (Exercise.)
- \(f\) is bounded if and only if \(f\) is \(O(1)\text{.}\) (Exercise.)
- \(O(g_1) O(g_2) = O(g_1 g_2)\text{.}\) (Exercise.)
- \(O(g_1) + O(g_2) = O(g_1 + g_2)\text{.}\) (Exercise.)
- \(\ll\) is transitive. (Exercise.)
Definition 4.1.3.
If \(f = O(g)\) and \(g = O(f)\) (that is, \(f \ll g\) and \(g \ll f\)) we write \(f \asymp g\) and say that \(f\) and \(g\) have the same order of magnitude.Example 4.1.4.
Two polynomials have the same order of magnitude if and only if they have the same degree. Two rational functions (ratios of polynomials) \(f/g\text{,}\) \(f'/g'\) have the same order of magnitude if and only if \(\deg f - \deg g = \deg f' - \deg g'\text{.}\)Exercise 4.1.5.
Is it true in general that \(f/g \asymp f'/g'\) if and only if \(f g' \asymp f' g\text{,}\) for any suitable functions \(f,f',g,g'\text{;}\) say assuming they are all strictly positive?
Subsection 4.1.2 Little o Notation
Definition 4.1.6.
For \(f,g : [a,\infty) \to \bbR\) with \(g(x) \gt 0\) for all \(x\text{,}\) we say \(f = o(g)\) (or \(f(x) = o(g(x))\)) if \(\lim_{x \to \infty} \frac{f(x)}{g(x)} = 0\text{.}\)
\(f = o(g)\) implies \(f = O(g)\text{,}\) but not conversely.
Definition 4.1.7.
For \(f, g : [a, \infty) \to \bbR\) we say \(f\) is asymptotic to \(g\text{,}\) denoted \(f \sim g\text{,}\) if \(\lim_{x \to \infty} \frac{f(x)}{g(x)} = 1\text{.}\) This makes sense as long as \(g(x) \neq 0\) for all sufficiently large \(x\text{;}\) we don’t need to assume \(g(x) \gt 0\) for all \(x\) in the domain.Example 4.1.8.
Two polynomials \(f,g\) are asymptotic (\(f \sim g\)) if and only if they have the same degree and the same leading coefficient.Even if \(f \sim g\text{,}\) the difference \(f-g\) may be unbounded. For example, \(x^2+x \sim x^2\text{,}\) but the difference \(x \to \infty\text{.}\) On the other hand, the relative difference \((f-g)/g \to 0\text{.}\)
