limit lemma

The limit lemma prescribes a way to compare order of function growth, which is useful for algorithm runtime analysis. To compare 2 algorithm runtimes, take the limit of one runtime over the other like so:

$$\underset{n\to \infty }{\lim }\frac{f(n)}{g(n)}=L$$

• if $L=0$, then $f(n)=O(g(n))$, i.e., $f$ grows asymptotically slower than $g$
• if $L\ne 0$ and is finite, then $f(n)=\Theta (g(n))$, i.e., $f$ grows roughly as fast as $g$
• if $L=\infty$, then $f(n)=\Omega (g(n))$, i.e., $f$ grows asymptotically faster than $g$