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.
2
$\begingroup$
$\endgroup$
-
$\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
1
$\begingroup$
$\endgroup$
$$\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}}$$
