# 13.8 Big-O

{% embed url="<https://www.youtube.com/watch?ab_channel=JoshHug&v=yG5mYNR3aIU>" %}

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.&#x20;