Big-O Notation and Asymptotics 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!
 A: 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|$.
A: 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$.
