3-1 Asymptotic behavior of polynomials

Let

$$ P(n) = \sum_{i=0}^d a_i n^i, $$

where $a_d > 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 > d$, then $p(n)=o(n^k)$

e. if $k < d$, then $p(n)=\omega(n^k)$

a

To prove $p(n)=O(n^k)$, we only need to prove:

$$ \begin{aligned} \sum_{i=0}^{d}a_in^i \leq cn^k (\text{ for }n \geq n_0)\cr \end{aligned} $$

Which is implied by

$$ \begin{aligned} c \geq \sum_{i=0}^da_in^{i-k} (\text{ for }n \geq n_0)\cr \end{aligned} $$ since $\sum_{i=0}^{d}a_i \geq \sum_{i=0}^da_in^{i-k} (\text{ for }n \geq 1)$

$\text{choose } c = \sum_{i=0}^{d}a_i$ and $n_0 = 1$ satisfies.

• Tips: the description of $n>n_0$ and $c$ will be omitted next time.

b

We only need to prove:

$$ \sum_{i=0}^{d}a_in^i \geq cn^k $$

which is implied by:

$$ \begin{aligned} c \leq \sum_{i=0}^da_in^{i-k}\cr c=a_d \leq \sum_{i=0}^da_in^{i-k}\cr n_0=1 \end{aligned} $$

c

We only need to prove:

$$ c_1n^d\leq \sum_{i=0}^{d}a_in^i \leq c_2n^{d} $$

which is implied by:

$$ \begin{aligned} c_1 \leq \sum_{i=0}^da_in^{i-d} \leq c_2\cr c_1=a_d \leq \sum_{i=0}^da_in^{i-d} \leq \sum_{i=0}^{d} a_i=c_2\cr n_0=1 \end{aligned} $$

d

We only need to prove: $$ \begin{aligned} \forall c >0,\exist n_0 \text{ satisfies: }\cr \sum_{i=0}^{d} a_i n^i < cn^k (\text{ for } n > n_0)\cr \impliedby c > \sum_{i=0}^{d} a_in^{i-k}\cr \text{since }\sum_{i=0}^{d} a_in^{d-k} \geq \sum_{i=0}^{d} a_in^{i-k}\cr n_0=\sqrt[d-k]{\frac {c} {\sum_{i=0}^d a_i}} \end{aligned} $$

e

We only need to prove: $$ \begin{aligned} \forall c >0,\exist n_0 \text{ satisfies: }\cr \sum_{i=0}^{d} a_in^i > cn^k (\text{ for }n>n_0)\cr \impliedby c < \sum_{i=0}^{d} a_in^{i-k}\cr \text{since } a_d n^{d-k} \leq \sum_{i=0}^{d} a_in^{i-k}\cr n_0=\sqrt[d-k]{\frac {c} {a_d}} \end{aligned} $$