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?
$\endgroup$2 Answers
$\begingroup$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$
$\endgroup$ 4 $\begingroup$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.
$\endgroup$ 2
