Asymptotic Notations
- Θ notation -
f(n) = Θ(g(n))
There exist positive constants
c
1
,
c
2
, and
n
0
such that
0 ≤ c
1
g(n) ≤ f(n) ≤ c
2
g(n) for all n ≥ n
0
.
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 n
0 such that
0 ≤ f(n) ≤ cg(n) for all n ≥ n
0
.
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 n
0 such that
0 ≤ cg(n) ≤ f(n) for all n ≥ n
0
.
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
n
0
> 0 such that 0 ≤ f(n) < cg(n) for all n ≥ n
0
.
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
lim
n→∞
(f(n)/g(n)) = 0
- ω notation -
f(n) = ω(g(n))
For any positive constant
c > 0
, there exists a constant
n
0
> 0 such that 0 ≤ cg(n) < f(n) for all n ≥ n
0
.
We say
f(n)
is
asymptotically bigger than
g(n)
if
f(n) = ω(g(n))
. We can also express this as the following limit.
lim
n→∞
(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.