Limit lemma

See: theta notation, Big-O notation, omega notation

Given \(f(n)\) and \(g(n)\), non-decreasing positive functions, then for \(\(\lim_{x \to \infty} \frac{f(x)}{g(x)}=L\)\) 1. If \(L=0\), then \(f(n)=O(g(n))\) 2. If \(L=c\), then \(f(n)= \theta(g(n))\) for some constant \(c\) 3. If \(L= \infty\), then \(f(n)= \Omega(g(n))\)