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:

• $N^3 + 3N^4 \in \Theta (N^4)$

• $N^3 + 3N^4 \in \text{O}(N^4)$

• $N^3 + 3N^4 \in \text{O}(N^6)$

• $N^3 + 3N^4 \in \text{O}(N^{N!})$

Formal Definition

$R(N) \in \text{O}(f(N))$ means that there exists positive constant $k_2$ such that: $R(N) \leq k_2 \cdot f(N)$ for all values of $N$ greater than some $N_0$ (a very large $N$).

Observe that this is a looser condition than $\Theta$ since O does not care about the lower bound.