1

Can someone show me how to start this off? I need to prove it, but I'm not sure how I would prove Big Omega.

Prove that $f(n)=\sum_{i=1}^ni^k\in\Omega(n^{k+1})$.

Thank you for the help!

Brian M. Scott
  • 616,228
user41580
  • 11
  • 1

1 Answers1

1

Note that $$\displaystyle\sum_{i = 0}^n i^k \geq \displaystyle\sum_{i = n/2}^n i^k \geq \displaystyle\sum_{i = n/2}^n \left(\frac{n}{2}\right)^k = \left(\frac{n}{2}\right)^{k+1}$$

I'll let you work out how to use that to get $\Omega(n^{k+1})$. (Remember that $k$ is a constant.)

Dennis Meng
  • 1,397
  • You can adjust the lower bound on the second and third sums to make the end result on the right exactly $\left(\frac{n}{2}\right)^{k+1}$; as posted it might be a slight bit off (though it doesn't affect the end result). – Dennis Meng Oct 20 '13 at 01:05