Reflexivity:
f(n) |
= |
Θ(f(n)), |
f(n) |
= |
O(f(n)), |
f(n) |
= |
Ω(f(n)). |
Symmetry:
f(n) = Θ(g(n)) if and only if g(n) = Θ(f(n)).
Transpose symmetry:
f(n) = O(g(n)) |
if and only if |
g(n) = Ω(f(n)), |
f(n) = o(g(n)) |
if and only if |
g(n) = ω(f(n)). |
Because these properties hold for asymptotic notations, one can draw an analogy between the asymptotic comparison of two functions f and g and the comparison of two real numbers a and b:
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. |
We say that f(n) is asymptotically smaller than g(n) if f(n) = o(g(n)), and f(n) is asymptotically larger than g(n) if f(n) = ω(g(n)).
One property of real numbers, however, does not carry over to asymptotic notation:
Trichotomy:For any two real numbers a and b, exactly one of the following must hold: a < b, a = b, or a > b.
Although any two real numbers can be compared, not all functions are asymptotically comparable. That is, for two functions f(n) and g(n), it may be the case that neither f(n) = O(g(n)) nor f(n) = Ω(g(n)) holds. For example, the functions n and n1 sin n cannot be compared using asymptotic notation, since the value of the exponent in n1 sin n oscillates between 0 and 2, taking on all values in between.