Tuesday, 1 October 2013

Big O notation for summation

Big O notation for summation

Consider the summation $$S(n)=1^c+2^c+3^c+...+n^c,$$ where c is some fixed
positive integer.
(a) Show that $S(n)$ is $O(n^{c+1})$
I did this part the following way, $S(n)$ is $O(n^{c+1})$ because $n^c
\leq n^{c+1}$ for $n \geq 1$. Is this correct? Can someone concur?
The second part is giving me trouble
(b) Show that $S(n)$ is $\Omega(n^{c+1})$
Do i do this the same way i solved the first part except now $n\leq 1$

No comments:

Post a Comment