Sep 15, 2024
Big O Notation (O)
f(n) = O(g(n))
if constants c > 0
and n₀
exist such that f(n) ≤ c * g(n)
for all n ≥ n₀
.f(n) = 2n + 3
can be represented as O(n)
by choosing an appropriate c
and g(n)
.O(n)
, O(n²)
) but the tightest bound is preferred.Big Omega Notation (Ω)
f(n) = Ω(g(n))
if constants c > 0
and n₀
exist such that f(n) ≥ c * g(n)
for all n ≥ n₀
.f(n) = 2n + 3
can also be Ω(log n)
, but the closer bound Ω(n)
is preferred.Theta Notation (Θ)
O(g(n))
and Ω(g(n))
for the same g(n)
.f(n) = Θ(g(n))
if there exist constants c1
, c2
, and n₀
such that c1 * g(n) ≤ f(n) ≤ c2 * g(n)
for all n ≥ n₀
.