Growth of Functions
- Θ notation -
f(n) = Θ(g(n))
There exist positive constants c1, c2, and n0 such that
0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0.
We say g(n) is an asymptotically tight bound for f(n) if f(n) = Θ(g(n)). Informally we can say, as far as time complexity or order of growth, these functions are equal.
- O notation -
f(n) = O(g(n)) There exist positive constants c and n0 such that
0 ≤ f(n) ≤ cg(n) for all n ≥ n0.
We say g(n) is an asymptotic upper bound for f(n) if f(n) = O(g(n)).
- Ω notation -
f(n) = Ω(g(n)) There exist positive constants c and n0 such that
0 ≤ cg(n) ≤ f(n) for all n ≥ n0.
We say g(n) is an asymptotic lower bound for f(n) if f(n) = Ω(g(n)).
- o notation -
f(n) = o(g(n)) For any positive constant c > 0, there exists a constant
n0 > 0 such that 0 ≤ f(n) < cg(n) for all n ≥ n0.
We say f(n) is asymptotically smaller than g(n) if f(n) = o(g(n)). We can also express this as the following limit
limn→∞(f(n)/g(n)) = 0
- ω notation -
f(n) = ω(g(n)) For any positive constant c > 0, there exists a constant
n0 > 0 such that 0 ≤ cg(n) < f(n) for all n ≥ n0.
We say f(n) is asymptotically bigger than g(n) if f(n) = ω(g(n)). We can also express this as the following limit.
limn→∞(f(n)/g(n)) = ∞
- Properties -
Transitivity:
f(n) = Θ(g(n)) and g(n) = Θ(h(n)) ⇒ f(n) = Θ(h(n)) f(n) = O(g(n)) and g(n) = O(h(n)) ⇒ f(n) = O(h(n)) f(n) = Ω(g(n)) and g(n) = Ω(h(n)) ⇒ f(n) = Ω(h(n)) f(n) = o(g(n)) and g(n) = o(h(n)) ⇒ f(n) = o(h(n)) f(n) = ω(g(n)) and g(n) = ω(h(n)) ⇒ f(n) = ω(h(n))
Reflexivity:
f(n) = Θ(f(n)) f(n) = O(f(n)) f(n) = Ω(f(n))
Symmetry:
f(n) = Θ(g(n)) iff g(n) = Θ(f(n))
Transpose symmetry:
f(n) = O(g(n)) iff g(n) = Ω(f(n)) f(n) = o(g(n)) iff g(n) = ω(f(n))
- Informal Comparison -
f(n) = O(g(n)) ≈ a ≤ b f(n) = Ω(g(n)) ≈ a ≥ b f(n) = Θ(g(n)) ≈ a = b f(n) = o(g(n)) ≈ a < b f(n) = ω(g(n)) ≈ a > b
- Note -
From the definitions of Θ, O, and Ω notations we can conclude the following: * For any two functions f(n) and g(n), we have f(n) = Θ(g(n)) iff f(n) = O(g(n)) and f(n) = Ω(g(n)). * If f(n) = O(g(n)) then g(n) = Ω(f(n)) and vice versa.