0
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ That is not correct because there are $n$ summands. $\endgroup$ – njguliyev Oct 1 '13 at 7:46
  • $\begingroup$ but they are all constants. cant you just ignore the constants because $n^c$ dominates them all? (i thought that was the point of Big O) $\endgroup$ – notamathwiz Oct 1 '13 at 7:47
3
$\begingroup$

Hint: Using the Stolz–Cesàro theorem prove $$\lim_{n\to \infty}\frac{S(n)}{n^{c+1}}=\frac1{c+1},$$ which answers both your questions.

$\endgroup$
0
$\begingroup$

For a), use the fact that $\sum_{k=1}^n k^c < \sum_{k=1}^n n^c = n^{c+1}$ for $n \ge 2$. This fact proves that $S(n) = O(n^{c+1})$, since you have found an $n_0$ and $M$ for which the inequality $S(n) < Mn^{c+1}$ always holds for $n \ge n_0$.

You can't just use the fact $n^c \le n^{c+1}$ and argue that the other terms are dominated, since it is exactly this you are supposed to prove.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.