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.

Last updated