# What's the big $O$ for this summation?

What would the big $O$ (worst-case runtime complexity; I think it's big $O$?) be for an algorithm that takes this long? I generalized the run time with the summation and put it in wolfram alpha.

$$\sum_{i = 0} ^{\sqrt n} i \sqrt n = \frac{1}{2} (\sqrt n + 1) n$$

I assume the actual run time would be the value on the right, so the big $O$ would be $n^{3/2}$? Please let me know if this is unclear. Thanks.

-
Yes, you're correct. If the runtime is as you claim $\frac{1}{2}(\sqrt{n} + 1)n$, then it is $O(n^{3/2})$ (and this is in fact easy to verify: by showing that $\frac{1}{2}(\sqrt{n}+1)n\cdot n^{-3/2}$ tends to a finite (nonzero) value, you will show that in fact $\frac{1}{2}(\sqrt{n} + 1)n$ is assymptotic to $n^{3/2}$, or, by definition, is $O(n^{3/2})$). – William Feb 15 '12 at 4:04
By the way, if $n$ is a square, then the sum above is very easy to compute by Gauss' summation formula: $1 + 2 +\cdots +m = (m + 1)/2$. You can do this without Mathematica. – William Feb 15 '12 at 4:07
And if $n$ is not a square, the summation is actually $$\sum_{i=0}^{\lfloor\sqrt{n}\rfloor}i\sqrt{n}=\sqrt{n}\sum_{i=0}^{\lfloor\sqrt{‌​n}\rfloor}i=\frac12\sqrt{n}{\lfloor\sqrt{n}\rfloor}({\lfloor\sqrt{n}\rfloor}i+1).‌​$$ – Brian M. Scott Feb 15 '12 at 4:10
In my experience, big O notation is used as a bound, not an asymptotic. So, in this case, your algorithm is $O(n^{3/2})$, but more is true: the algorithm is $\Theta(n^{3/2})$, and on the exact order of (`$\sim$') $n^{3/2}/2$. – A Walker Feb 15 '12 at 4:10
thanks for the responses. if anyone wants to leave an answer i'll accept it. – Marty Feb 15 '12 at 4:16

## 1 Answer

Yes, you're correct. If the runtime is as you claim 12(n√+1)n, then it is O(n3/2) (and this is in fact easy to verify: by showing that 12(n√+1)n⋅n−3/2 tends to a finite (nonzero) value, you will show that in fact 12(n√+1)n is assymptotic to n3/2, or, by definition, is O(n3/2)).

-
Well this is a bit odd. You answered your own question and accepted it yourself. Just found it a bit funny though the answer seems completely plausible – dashdart Apr 18 '12 at 9:57
@biditacharya yeah it's been a few months and no one took it, even though there were acceptable answers as comments. not sure why no one stuck an answer in. – Marty Apr 18 '12 at 10:27