5
$\begingroup$

I realize that this is not a typical programing question but its still related. If anyone could help me out I would really appreciate it because I have a midterm coming up and this is the part that I don't understand. This is not a homework problem so don't worry about me trying to get out of my work. I just need someone to explain how to do this is normal plain english instead of whatever my professor is using.

Let $p(n) = \sum_{i=0}^d a_i n^i$ where $a_i,d > 0$ be a polynomial in $n$ of degree $d$. Use the definitions of the asymptotic notations to prove the following properties:

a) If $k \geq d$, then $p(n) = O(n^k)$.

There are also 4 more correspoding to the Omega, theta small o and small omega properties but if I could get an idea on how to start I can figure the other ones out on my own. Thanks so Much!

$\endgroup$
5
$\begingroup$

All students have difficulties when they meet the $O$- and the $o$-notations for the first time. Whenever such an $O$ appears it refers to a pre-agreed limit process for the independent variable, in the case at stake to $n\to\infty$. The statement $p(n)=O(n^k)\ (n\to\infty)$ does not mean that the (usually "complicated") function $p(n)$ is equal to some other function $O(\cdot)$, evaluated at $n^k$. Instead it expresses the (claimed or proven) fact that the function $p(n)$ under study, after division by $n^k$, stays bounded when $n\to\infty$; which is the same thing as saying that $p(n)=b(n)\cdot n^k$ where now $b(n)$ is a bounded function. In your example, each $n^i/n^k$ is $\leq 1$, so in fact $|p(n)|\leq C\cdot n^k$ with $C:=\sum_{i=1}^d |a_i|$.

$\endgroup$
  • $\begingroup$ I really appreciate your help. So how do you know what b(n) is or is that arbitrary? Also, how do you know that n^i/n^k is <=1? with that being said, how do you know that the size of |p(n)| (thats what the | | means correct?) is <= Cn^k? $\endgroup$ – user7538 Feb 27 '11 at 17:46
2
$\begingroup$

For (a) we want to show that $p(n) = O(n^k)$ for $k \geq d$. This is the same thing as showing that there exists a positive number $M$ and a real number $n_0$ such that $|p(n)| \leq M|n^k|$ for all $n>n_0$. So we have

$$|a_{0}+a_{1}n+a_{2}n^2 + \cdots +a_{d}n^d| \leq a_{d}n^{d} +a_{d-1}n^d + \cdots+ a_{0}n^d$$

$$\leq (a_0+ a_1 + \cdots + a_d)n^d$$

$$ \ \leq (a_0+ a_1 + \cdots + a_d)|n^d|$$

So $f(n) = O(n^d) \implies f(n) = O(n^k)$ for $k \geq d$.

$\endgroup$
  • $\begingroup$ I really appreciate your help but im a little confused, where does the k come into play? also how did you know to factor out the a's and have all the n's raised to the d power? $\endgroup$ – user7538 Feb 27 '11 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy