Comment on page

13.8 Big-O

Not to be confused with Big-Theta.
O (pronounced "Big-Oh") is similar to
Θ\Theta
. Instead of being an "equality" on the order of growth, it can be though of as "less than or equal."
For example, the following statements are all true:
  • N3+3N4Θ(N4)N^3 + 3N^4 \in \Theta (N^4)
  • N3+3N4O(N4)N^3 + 3N^4 \in \text{O}(N^4)
  • N3+3N4O(N6)N^3 + 3N^4 \in \text{O}(N^6)
  • N3+3N4O(NN!)N^3 + 3N^4 \in \text{O}(N^{N!})

Formal Definition

R(N)O(f(N))R(N) \in \text{O}(f(N))
means that there exists positive constant
k2k_2
such that:
R(N)k2f(N)R(N) \leq k_2 \cdot f(N)
for all values of
NN
greater than some
N0N_0
(a very large
NN
).
Observe that this is a looser condition than
Θ\Theta
since O does not care about the lower bound.