Big O Notation

Definition

Function r has order of growth $O(g(n))$ if there is a positive constants $k$ and a number $n_0$ such that $r(n)\le k\cdot g(n)$ for all $n>n_0$

Explanation

• The amount of resources cannot be more than $O(g(n))$

Notes

• If a function has a time complexity of $\Theta (n)$, we can say it’s order of growth is $O(n)$ or $O(n^2)$ etc.
  • This is because the only requirement for big O is that $r(n)\le k\cdot g(n)$