Definition

Analyzing how two functions $f$ and $g$ grow in comparison.

1. $f=O(g)$: going toward infinity, $f$ grows at most as fast as g
2. $f=\mathrm{\Omega }(g)$: going toward infinity, f grows at least as fast as g
3. $f=\theta (g)$: when $f=O(g)$ and $f=\mathrm{\Omega }(g)$
   • f grows comparable to g

How to compute

Limit

Calculate the limit of $\frac{f(n)}{g(n)}$ when $n\to \mathrm{\infty }$

• $limit=0$: $f=O(g)$
• $limit=\mathrm{\infty }$: $f=\mathrm{\Omega }(g)$
• $limit=const$: $f=\theta (g)$

For polynomials

1. Keep the biggest exponent, throw everything else away.
2. Remove the multiplier