How can I prove this complexity?

$$\sum_{k=1}^n \sqrt{k}=\Theta(n\sqrt{n})$$

The theta notation means a quantity bounded in the limit both above and below by constant multiples of the given expression.

  • $\begingroup$ @DavidMitra Surely the $\sqrt n$ is intended to be a $\sqrt i$. $\endgroup$ – Pedro Tamaroff Oct 6 '13 at 14:58
  • $\begingroup$ For $\sum_{k=1}^n\sqrt k$: Do you know Euler-Maclaurin formula? Or Stolz-Cesàro theorem? $\endgroup$ – Yai0Phah Oct 6 '13 at 15:06
  • $\begingroup$ With this new edit it looks even more hilarious :) $\endgroup$ – user0810 Oct 6 '13 at 15:08
  • $\begingroup$ sorry again !that is first Question ! $\endgroup$ – Fefaeze Aezaza Zaeezez Oct 6 '13 at 15:11
  • $\begingroup$ Does anyone here but the OP know what that $\;\theta\;$ there means?! $\endgroup$ – DonAntonio Oct 6 '13 at 15:50

$$\sum_{i=1}^n \sqrt{i} \leq \sum_{i=1}^n \sqrt{n}=n \sqrt{n}$$ and $$\sum_{i=1}^n \sqrt{i} \geq \sum_{i=\lfloor \frac{n+1}{2} \rfloor}^n \sqrt{i} \geq \sum_{i=\lfloor \frac{n+1}{2} \rfloor}^n \sqrt{\frac{n}{2}} \geq \frac{n-1}{2} \sqrt{\frac{n}{2}}= \frac{n\sqrt{n}}{2 \sqrt{2}}-\sqrt{\frac{n}{8}}$$


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.