Chapter 3, Problem 1P

(a)

Program Plan Intro

To prove that the asymptotic notation $p\left(n\right)=O\left(n^k\right)$ where $k\ge d$ .

Explanation of Solution

Given Information:Let $p\left(n\right)={\displaystyle \sum _{i=0}^d{a}_i{n}^i}$ be a polynomial of degree d and k be a constant.

Explanation:

Consider that there exists some constants $c,n_0>0$ such that $0\le p\left(n\right)\le c\cdot n^k$ for all $n\ge n_0$ .

  $\begin{array}{l}p\left(n\right)={\displaystyle \sum _{i=0}^d{a}_i{n}^i}\\ =a_0+a_1{n}^1+a_2{n}^2+\cdots a_k{n}^k+\cdots +a_d{n}^d\\ \le {\displaystyle \sum _{i=0}^d{a}_i}\end{array}$

The last line ensures the fact that $k\ge d$ for all value of iand $n^{i-k}\le 1$ for all $n\ge 1$ .

Therefore, $p\left(n\right)=O\left(n^k\right)$ is true for the asymptotic notation of $p\left(n\right)={\displaystyle \sum _{i=0}^d{a}_i{n}^i}$ where $c={\displaystyle \sum _{i=0}^d{a}_i}$ and $n_0=1$ .

(b)

Program Plan Intro

To prove that the asymptotic notation $p\left(n\right)=\Omega \left(n^k\right)$ where $k\le d$ .

Explanation of Solution

Explanation:

Consider that there exists some constants $c,n_0>0$ such that $0\le c\cdot n^k\le p\left(n\right)$ for all $n\ge n_0$ .

  $\begin{array}{l}p\left(n\right)={\displaystyle \sum _{i=0}^d{a}_i{n}^i}\\ =a_0+a_1{n}^1+a_2{n}^2+\cdots a_k{n}^k+\cdots +a_d{n}^d\\ \ge a_k{n}^k\end{array}$

The last line ensures the fact that $k\le d$ for all value of isuch that $0\le c\cdot n^k\le p\left(n\right)$ where $c=a_k$ and $n_0=1$ .

Therefore, $p\left(n\right)=\Omega \left(n^k\right)$ is true for the asymptotic notation of $p\left(n\right)={\displaystyle \sum _{i=0}^d{a}_i{n}^i}$ where $k\le d$ .

(c)

Program Plan Intro

To prove that the asymptotic notation $p\left(n\right)=\theta \left(n\right)$ where $k\le d$ .

Explanation of Solution

Explanation:

Consider that there exists some constants $c,n_0>0$ such that $0\le c\cdot n^k\le p\left(n\right)$ for all $n\ge n_0$ .

It is already proved that for $k=d$ , $p\left(n\right)=O\left(n\right)$ and $p\left(n\right)=\Omega \left(n\right)$

Therefore, $p\left(n\right)=\theta \left(n\right)$ is true for the asymptotic notation of $p\left(n\right)={\displaystyle \sum _{i=0}^d{a}_i{n}^i}$ where $k=d$ .

(d)

Program Plan Intro

To prove that the asymptotic notation $p\left(n\right)=o\left(n^k\right)$ where $k>d$ .

Explanation of Solution

Explanation:

It can be easily prove by removing the equality from the part (a).

The limit definition of $o-$ notation is as follows:

  $\begin{array}{c}\underset{n\to \infty }{\lim }\frac{p\left(n\right)}{n^k}=\underset{n\to \infty }{\lim }\frac{{\displaystyle \sum _{i=0}^d{a}_i{n}^i}}{n^k}\\ =\underset{n\to \infty }{\lim }\frac{a_d{n}^d}{n^k}\\ =0\end{array}$

The limit is equal to 0since $k>d$ .

Therefore, $p\left(n\right)=o\left(n\right)$ is true for the asymptotic notation of $p\left(n\right)={\displaystyle \sum _{i=0}^d{a}_i{n}^i}$ where $k>d$ .

(e)

Program Plan Intro

To prove that the asymptotic notation $p\left(n\right)=\omega \left(n\right)$ where $k<d$ .

Explanation of Solution

Explanation:

It can be easily prove by removing the equality from the part (b).

The limit definition of $\omega -$

notation is as follows:

  $\begin{array}{c}\underset{n\to \infty }{\lim }\frac{p\left(n\right)}{n^k}=\underset{n\to \infty }{\lim }\frac{{\displaystyle \sum _{i=0}^d{a}_i{n}^i}}{n^k}\\ =\underset{n\to \infty }{\lim }\frac{a_d{n}^d}{n^k}\\ =\infty \end{array}$

The limit is equal to $\infty$ since $k<d$ .

Therefore, $p\left(n\right)=\omega \left(n\right)$ is true for the asymptotic notation of $p\left(n\right)={\displaystyle \sum _{i=0}^d{a}_i{n}^i}$ where $k<d$ .