3-1

3-1 Asymptotic behavior of polynomials Let $$p(n) = \sum\limits_{i=0}^d a_i n^i$$ where $a_d \gt 0$, be a degree-d polynomial in n, and let k be a constant. Use the definitions of the asymptotic notations to prove the following properties.
 a. If $k \geq d$, then $p(n) = O(n^k) $
 b. If $k \leq d$, then $p(n) = \Omega(n^k)$.
 c. If $k = d$, then $p(n) = \theta(n^k)$.
 d. If $k \gt d$, then $p(n) = o(n^k)$.
 e. If $k \lt d$, then $p(n) = \omega(n^k)$.
solution:
 a. If $k \geq d$, then $p(n) = O(n^k)$ by definition of big-oh of n $0\leq f(n) \leq cg(n)$ we can write the functions as $0 \leq \sum\limits_{i=0}^d a_i n^i \leq c n^k$
divide the equation by $n^k$
$$0 \leq {{\sum\limits_{i=0}^d a_i n^i}\over n^k} \leq c $$ $$0 \leq \sum\limits_{i=0}^d a_i n^{i-k} \leq c $$ Now since $k \geq d$ then $i-k \leq 0$ and all $n^{i-k}$ will be less than 1 so if we choose $c = \sum\limits_{i=0}^d a_i $ then the equation will be true.
  b. If $k \leq d$, then $p(n) = \Omega(n^k)$. by definition of big-omega of n $0 \leq cg^n \leq f^n$ we can write the functions as $0 \leq c n^k \leq \sum\limits_{i=0}^d a_i n^i $
divide the equation by $n^k$
$$0 \leq c \leq {{\sum\limits_{i=0}^d a_i n^i} \over n^k} $$ $$0 \leq c \leq \sum\limits_{i=0}^d a_i n^{i-k} $$ Now since $k \leq d $ then $i-k \geq 0$ for large values of i $(i>k)$ and $n^{i-k}$ will be greater than 1 so if we choose $c = \sum\limits_{i=0}^d a_i $ then the equation will be true.
 c. If $k = d$, then $p(n) = \theta(n^k)$ by definition of $\theta(n)$ $0 \leq c_1 n^k \leq \sum\limits_{i=0}^d a_i n^i \leq c_2 n^k$ dividing equation by $n^k$ $$0 \leq c_1 \leq {{\sum\limits_{i=0}^d a_i n^i} \over n^k} \leq c_2 $$ $$0 \leq c_1 \leq \sum\limits_{i=0}^d a_i n^{i-k} \leq c_2 $$ lets get c1 and c2 values which satisfy the equation $$ c_1 \leq \sum\limits_{i=0}^d a_i n^{i-k}$$ since $k = d$ then the $i-k \leq 0 $ and $n^{i-k}$ will be less than 1
I find it easier to find values of c1 and c2 by taking examples(induction principle) ex: let k =1 and n = 1 since k = d then d = 1 $$ c_1 \leq \sum\limits_{i=0}^1 a_i n^{i-k}$$ $$ c_1 \leq a_0 n^{0-1}+ a_1 n^{1-1} $$ $$ c_1 \leq a_0 n^-1+ a_1 $$ if $c_1$ is a_1 (is $a_d$ in this example ) the above equation is always true if we do the same for k = 1,2 ... d $c_1 = a_d$ will prove the equation correct always Lets find c2 now $$c_2 \geq \sum\limits_{i=0}^d a_i n^{i-k}$$ ex: let k =1 and n = 1 since k = d then d = 1 $$c_2 \geq a_0 n^{0-1}+ a_1 n^{1-1} $$ $$ c_2 \geq a_0 n^-1+ a_1 $$ if $$ c_2 = a_0+a_1$$ the above equation is always true which is sum of coefficients of polynomial $$ c_2 = \sum\limits_{i=0}^1 a_i$$ if we do the same for k = 1,2 ... d $$ c_2 = \sum\limits_{i=0}^d a_i$$
Similarly we can prove other equation above.