> For the complete documentation index, see [llms.txt](https://cs61b-2.gitbook.io/cs61b-textbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs61b-2.gitbook.io/cs61b-textbook/13.-asymptotics-i/13.8-big-o.md).

# 13.8 Big-O

Not to be confused with Big-Theta.

{% 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;