GROWTH RATES AND ASYMPTOTIC NOTATIONS

Goal:

• Categorize algorithms based on their asymptotic growth rate.

• Ignore (small) constant of proportionality $\&$ small inputs

• Estimate upper bound on growth rate of time complexity function

def1: (For arbitrary functions) $f(n)\in O(g(n))$ if there exist two positive constants $c$ and $n_{0}$ such that

$$\vert f(n)\vert\leq c\vert g(n)\vert$$

for all $n\geq n_{0}.$

eg.

1. $f(n)=5n$ $g(n)=n^{2}$

   $5n_{0} \leq cn_{0}^{2}$
   $\Rightarrow 5 \leq cn_{0}$
   $\Rightarrow n_{0}=5,c=1$
   Thus, $5n=O(n^{2})$

2. $f(n)=10^{6}n^{2}$ $g(n)=n^{2}$

   To prove: $(10^{6}n^{2})\leq cn^{2}$ for $n\geq n_{0}$
   choose $C=10^{6}$
   Then $n_{0}=1$
   $\Rightarrow (10^{6}n^{2})=O(n^{2})$
   

3. $A(n)=a_{m}n^{m}+ a_{m-1}n^{m-1}+\ldots +a_{1}n+a_{0}$

   a polynominal of degree $m$, $n,m\geq 0$ for all $i$, $a_{i}\in R$
   
   To Prove: $A(n)=O(n^{m})=a_{m}n^{m}+O(n^{m-1})$

   Example: $5n^3 + 2n^2 - 5 = O(n^3) = 5n^3 + O(n^2)$
   Proof:
   To Prove: $\vert A(n)\vert \leq c\vert n^m\vert$
   
   $\vert A(n)\vert\leq \vert a_{m}\vert n^{m}+\vert a_{m-1}\vert n^{m-1}+\ldots +\vert a_{1}\vert n+\vert a_{0}\vert$
   
   $\leq n^{m}(\vert a_{m}\vert+\frac{\vert a_{m-1}\vert}{n}+\ldots+\frac{\vert a_{1}\vert}{n^{m-1}} +\frac{\vert a_{0}\vert}{n^{m}})$
   
   $\leq n^{m}(\vert a_{m}\vert+\vert a_{m-1}\vert+\ldots +\vert a_{0}\vert)$
   
   
   $c=\vert a_{m}\vert+\vert a_{m-1}\vert+\cdots+\vert a_{0}\vert$
   
   $n_{0}=1$
   
   Example: $5n^3 + 2n^2 - 5 = O(n^3)$
   c = $5 + 2 + \vert-5\vert$ = 12
   

   $5n^3 + 2n^2 - 5 \leq 12n^3$
   for all $n\geq 1$.