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

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.

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