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:
​N3+3N4∈Θ(N4)N^3  + 3N^4 \in \Theta (N^4)N3+3N4∈Θ(N4)
​
​N3+3N4∈O(N4)N^3 + 3N^4 \in \text{O}(N^4)N3+3N4∈O(N4)
​
​N3+3N4∈O(N6)N^3 + 3N^4 \in \text{O}(N^6)N3+3N4∈O(N6)
​
​N3+3N4∈O(NN!)N^3 + 3N^4 \in \text{O}(N^{N!})N3+3N4∈O(NN!)
​
Formal Definition
​R(N)∈O(f(N))R(N) \in \text{O}(f(N))R(N)∈O(f(N))
 means that there exists positive constant k2k_2k2​
 such that:
R(N)≤k2⋅f(N)R(N) \leq k_2 \cdot f(N)R(N)≤k2​⋅f(N)
 for all values of NNN
 greater than some N0N_0N0​
 (a very large NNN
).
Observe that this is a looser condition than Θ\ThetaΘ
 since O does not care about the lower bound. 

13.7 Big-Theta

13.9 Summary

Last modified 9mo ago