13.8 Big-O

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.