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:

- $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!})$

$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. Last modified 9mo ago