def3:

$f\in O(g)$ if $\lim_{n \rightarrow \infty} \frac{f(n)}{g(n)}\rightarrow c$ for some $c \in R^{*}.$

Examples:

1. $10^{6}n^{2}=O(n^{2})$
   $\lim_{n \rightarrow \infty} \frac{10^{6}n^{2}}{n^{2}}\rightarrow 10^{6}$
   
2. $5n \in O(n^2)$
   $\lim_{n \rightarrow \infty} \frac{5n}{n^{2}} \rightarrow 0$
   
   
   
3. Prove that $2^{n}\neq O(n^{m})$ for any integer $m$.
   
   (By Contradiction:) Suppose $2^{n}=O(n^{m})$
   
   $\lim_{n \rightarrow \infty} \frac{2^{n}}{n^{m}}= \lim_{n \rightarrow \infty} \frac{2^{n}\log 2}{mn^{m-1}}$
   
   $=\lim_{n \rightarrow \infty} \frac{{(\log 2)}^2 2^{n}}{m(m-1)n^{m-2}}$
   
   $=\lim_{n \rightarrow \infty} \frac{(\log 2)^{m}2^{n}}{m(m-1)\cdots(2)1}$ $\rightarrow \infty$
   
   Thus, polynomial algorithms are distinctly superior to exponential-time algorithms.
   

(Project should have polynomial algo's only)