Asymptotic behavior of polynomials

Question

The following question is taken from Introduction to Algorithms by CLRS, Chapter $3.$

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).$

a. If $k< d,$ then $p(n)= \omega(n^k).$

My attempt:

From exercise $3.1$-$1$ in the same chapter, we have proven that for asymptotically nonnegative function $f(n)$ and $g(n),$ $$max(f(n),g(n)) = \Theta(f(n)+g(n)).$$ So we have $$\Theta(f(n)+g(n)) = \Theta(max(f(n),g(n))).$$ It follows that $$p(n) = \Theta(p(n)) = \Theta\left( \sum_{i=0}^d a_i n^i \right) = \Theta(n^d).$$ So all parts (a)-(e) follow.

Is my attempt above correct?

Answer 1

I recommend that you think about your definitions a bit.

Consider the function in the sum: $\sum_{i=0}^d{a_i n^i} = a_d n^d + a_{d-1} n^{d-1} + a_{d-2}n^{d-2} + \dots$

Now, the question told you that the function is a polynomial in $n$. Believe it or not, that means that only $n$ really matters in asymptotic notation.

Going back to our function:

$\begin{align} \sum_{i=0}^d{a_i n^i} &= a_d n^d + \dots \\ &= \Theta{n^d} \\ &= O(n^{d+1}) \\ &= O(n^{d} \\ &= o(n^{d+1}) \\ &\ne o(n^d) \\ &= \omega(n^{d-1}) \\ &\ne \omega(n^d) \\ &= \Omega(n^{d-1}) \\ &= \Omega(n^d) \end{align}$

I hope this helps. Keep looking at the definitions, and think that they're all really about $n$ and that they're functions of $n$, polynomials of $n$.

Just add comments below if you need more help.

Answer 2

You are using:

$\displaystyle 0<\lim\limits_{n\to a}\inf\left|\frac{\max(f(n),g(n))}{f(n)+g(n)}\right|\leq\lim\limits_{n\to a}\sup\left|\frac{\max(f(n),g(n))}{f(n)+g(n)}\right|<\infty~$

We get a problem, if $~f~$ and $~g~$ are polynomials and at least one is no constant:

$\max(f(n),g(n))=~\infty~$

It's impossible to use your argumentation, it's better to use the definitions:

a. $\displaystyle ~p(n)= O(n^k) :~~\lim\limits_{n\to\infty}\sup\left|\frac{p(n)}{n^k}\right|<\infty$

b. $\displaystyle ~p(n)= \Omega(n^k) :~~\lim\limits_{n\to\infty}\inf\left|\frac{p(n)}{n^k}\right|>0~$

c. $\displaystyle ~p(n)= \Theta(n^k) :~~0<\lim\limits_{n\to\infty}\inf\left|\frac{p(n)}{n^k}\right|\leq\lim\limits_{n\to\infty}\sup\left|\frac{p(n)}{n^k}\right|<\infty~$ , $~$it's $~$a.$~$ and $~$b.

d. $\displaystyle ~p(n)= o(n^k) :~~\lim\limits_{n\to\infty}\left|\frac{p(n)}{n^k}\right|= 0$

e. $\displaystyle ~p(n)= \omega(n^k) :~~\lim\limits_{n\to\infty}\left|\frac{p(n)}{n^k}\right|= \infty$