Big-O Notation

Relevant Classes: EECS 281, EECS 376

The Asymptotic Upper Bound for a function in the following regard: $f(n)=O(g(n))⟺\exists c>0\wedge n_0\ge 0\text{ s.t. }\forall n\ge n_0,f(n)\le c\cdot g(n)$ A sufficient (but not necessary) condition:

If ${\lim }_{n\to \infty }\left(\frac{f(n)}{g(n)}\right)=d<\infty$, then $f(n)$ is $O(g(n))$.

Note: Since this is just a sufficient (but not necessary) condition, if the limit is not a non-infinite constant, that does not mean that $f(n)\ne O(g(n))$.

This is similar to and related to: Big-Theta and Big-Omega