3 Bachman-Landau notation
Bachman-Landau family of notations is the name of a few closely related notations used in algorithm analysis. The most famous of them is the so-called big-O notation. While most formulations are defined on functions from naturals or reals to reals, we define them more generally - requirements for the types of the domain and codomain vary between different properties. However, all properties hold for functions from a linearly ordered commutative ring to a linearly ordered field. In the rest of this page, we let \(R\) be a linearly ordered commutative ring and \(F\) be a linearly ordered field. We will also use symbols \(f\), \(f\_ 1\), \(f\_ 2\), \(g\), \(g\_ 1\) and \(g\_ 2\) for functions \(R \to F\). Also, we let \(M\) be a right \(R\)-module, although often only a (distributive) left multiplicative action on \(R\) is required.
3.1 Asymptotic sets
(Big O notation) \(f(x) \in O(g(x))\) if it is asymptotically bounded above by \(g(x)\).
(Big Omega notation) \(f(x) \in \Omega (g(x))\) if it is asymptotically bounded below by \(g(x)\).
(Big Theta notation) \(f(x) \in \Theta (g(x))\) if it is asymptotically bounded by \(g(x)\).
(Small O notation) \(f(x) \in o(g(x))\) if it is asymptotically dominated by \(g(x)\).
(Small Omega notation) \(f(x) \in \omega (g(x))\) if it asymptotically dominates \(g(x)\).
3.2 Relations between asymptotic sets
If \(f(x) \in o(g(x))\), then \(f(x) \in O(f(x))\).
Since \(o(g(x))\) and \(O(f(x))\), we can simply use Lemma 35.
If \(f(x) \in \omega (g(x))\), then \(f(x) \in \Omega (g(x))\).
The proof is a simple application of Theorem 36.
\(f(x) \in O(g(x))\) and \(f(x) \in \Omega (g(x))\) if and only if \(f(x) \in \Theta (g(x))\).
Similarly to previous proofs, the proof is a direct application of Lemma 37.
Let \(g\) be asymptotically positive. Then \(f(x) \in \Theta (g(x))\) and \(f(x) \in o(g(x))\) are not both true.
A direct application of Lemma 38.
Let \(g\) be asymptotically positive. If \(f(x) \in \Theta (g(x))\) then \(f(x) \notin o(g(x))\).
A direct application of Lemma 80.
Let \(g\) be asymptotically positive. If \(f(x) \in o(g(x))\) then \(f(x) \notin \Theta (g(x))\).
A direct application of Lemma 80.
Let \(g\) be asymptotically positive. If \(f(x) \in \Omega (g(x))\) then \(f(x) \notin o(g(x))\).
A direct application of Lemma 39.
Let \(g\) be asymptotically positive. If \(f(x) \in o(g(x))\) then \(f(x) \notin \Omega (g(x))\).
A direct application of Lemma 40.
Let \(g\) be asymptotically positive. Then \(f(x) \in \Theta (g(x))\) and \(f(x) \in \omega (g(x))\) are not both true.
A direct application of Lemma 41.
Let \(g\) be asymptotically positive. If \(f(x) \in \Theta (g(x))\) then \(f(x) \notin \omega (g(x))\).
A direct application of Lemma 85.
Let \(g\) be asymptotically positive. If \(f(x) \in \omega (g(x))\) then \(f(x) \notin \Theta (g(x))\).
A direct application of Lemma 85.
Let \(g\) be asymptotically positive. Then \(f(x) \in o(g(x))\) and \(f(x) \in \omega (g(x))\) are not both true.
A direct application of Lemma 44.
Let \(g\) be asymptotically positive. If \(f(x) \in o(g(x))\) then \(f(x) \notin \omega (g(x))\).
A direct application of Lemma 88.
Let \(g\) be asymptotically positive. If \(f(x) \in o(g(x))\) then \(f(x) \notin \omega (g(x))\).
A direct application of Lemma 88.
3.3 Reflexivity
\(f(x) \in \Theta (f(x))\).
Direct consequence of Lemma 47.
\(f(x) \in O(f(x))\).
This follows directly from Lemma 48.
\(f(x) \in \Omega (f(x))\).
This follows directly from Lemma 49.
3.4 Transitivity
If \(f(x) \in O(g(x))\) and \(g(x) \in O(h(x))\), then \(f(x) \in O(h(x))\).
This follows directly from Lemma 50.
If \(f(x) \in \Omega (g(x))\) and \(g(x) \in \Omega (h(x))\), then \(f(x) \in \Omega (h(x))\).
This follows directly from Lemma 51.
If \(f(x) \in \Theta (g(x))\) and \(g(x) \in \Theta (h(x))\), then \(f(x) \in \Theta (h(x))\).
This follows directly from Lemma 52.
If \(f(x) \in o(g(x))\) and \(g(x) \in o(h(x))\), then \(f(x) \in o(h(x))\).
This follows directly from Lemma 53.
If \(f(x) \in \omega (g(x))\) and \(g(x) \in \omega (h(x))\), then \(f(x) \in \omega (h(x))\).
This follows directly from Lemma 54.
3.5 Scalar multiplicativity
Let \(c {\gt} 0\). If \(f(x) \in O(g(x))\), then \(c \cdot f(x) \in O(g(x))\).
This follows directly from Lemma 55.
Let \(c {\gt} 0\). If \(f(x) \in \Omega (g(x))\), then \(c \cdot f(x) \in \Omega (g(x))\) is also bounded below by \(g\).
This follows directly from Lemma 56.
Let \(c {\gt} 0\). If \(f(x) \in \Theta (g(x))\), then \(c \cdot f(x) \in \Theta (g(x))\).
This follows directly from Lemma 57.
Let \(c {\lt} 0\). If \(f(x) \in O(g(x))\), then \(c \cdot f(x) \in O(-g(x))\).
This follows directly from Lemma 58.
Let \(c {\lt} 0\). If \(f \in \Omega (g(x))\), then \(c \cdot f(x) \in \Omega (-g(x))\).
This follows directly from Lemma 59.
Let \(c {\lt} 0\). If \(f(x) \in \Theta (g(x))\), then \(c \cdot f \in \Theta (-g(x))\).
This follows directly from Lemma 60.
3.6 Additivity
Let \(f\_ 1(x), f\_ 2(x) \in O(g(x))\). Then \(f\_ 1(x) + f\_ 2(x) \in O(g(x))\).
This follows directly from Lemma 61.
Let \(f\_ 1(x), f\_ 2(x) \in \Omega (g(x))\). Then \(f\_ 1(x) + f\_ 2(x) \in \Omega (g(x))\).
This follows directly from Lemma 62.
Let \(f\_ 1(x), f\_ 2(x) \in \Theta (g(x))\). Then \(f\_ 1(x) + f\_ 2(x) \in \Theta (g(x))\).
This follows directly from Lemma 63.
Let \(f\_ 1(x) \in \Omega (g(x))\) and let \(f\_ 2\) be asymptotically positive. Then \(f\_ 1(x) + f\_ 2(x) \in \Omega (g(x))\).
This follows directly from Lemma 64.
Let \(f\_ 1(x) \in O(g(x))\) and let \(f\_ 2\) be asymptotically negative. Then \(f\_ 1(x) + f\_ 2(x) \in O(g(x))\).
This follows directly from Lemma 65.
Let \(f\_ 1(x) \in \Theta (g(x))\). Let also \(f\_ 2\) be asymptotically positive and \(f\_ 2(x) \in O(g(x))\). Then \(f\_ 1(x) + f\_ 2(x) \in \Theta (g(x))\).
This follows directly from Lemma 66.
Let \(f\_ 1(x) \in \Theta (g(x))\). Let also \(f\_ 2\) be asymptotically negative and \(f\_ 2(x) \in \Omega (g(x))\). Then \(f\_ 1(x) + f\_ 2(x) \in \Theta (g(x))\).
This follows directly from Lemma 67.
Let \(f\_ 1(x) \in \Theta (g(x))\). Let also \(f\_ 2\) be asymptotically positive and \(f\_ 2(x) \in o(g(x))\). Then \(f\_ 1(x) + f\_ 2(x) \in \Theta (g(x))\).
This follows directly from Lemma 68.
Let \(f\_ 1(x) \in \Theta (g(x))\). Let also \(f\_ 2\) be asymptotically negative and \(f\_ 2(x) \in \omega (g(x))\). Then \(f\_ 1(X) + f\_ 2(x) \in \Theta (g(x))\).
This follows directly from Lemma 69.
3.7 Multiplicativity
Let \(f\_ 1\) and \(f\_ 2\) be asymptotically nonnegative functions such that \(f\_ 1(x) \in O(g\_ 1(x))\) and \(f\_ 2(x) \in O(g\_ 2(x))\). Then \(f\_ 1(x) * f\_ 2(x) \in O(g\_ 1(x) * g\_ 2(x))\).
This follows directly from Lemma 70.
Let \(f\_ 1\) and \(f\_ 2\) be asymptotically nonpositive functions such that \(f\_ 1(x) \in \Omega (g\_ 1(x))\) and \(f\_ 2(x) \in \Omega (g\_ 2(x)\). Then \(f\_ 1(x) * f\_ 2(x) \in \Omega (g\_ 1(x) * g\_ 2(x))\).
This follows directly from Lemma 71.