0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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})$). $\endgroup$ – user2093 Feb 15 '12 at 4:04
  • $\begingroup$ 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. $\endgroup$ – user2093 Feb 15 '12 at 4:07
  • $\begingroup$ 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).$$ $\endgroup$ – Brian M. Scott Feb 15 '12 at 4:10
  • $\begingroup$ 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$. $\endgroup$ – awwalker Feb 15 '12 at 4:10
  • $\begingroup$ thanks for the responses. if anyone wants to leave an answer i'll accept it. $\endgroup$ – Marty Feb 15 '12 at 4:16
0
$\begingroup$

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)).

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – funktor Apr 18 '12 at 9:57
  • $\begingroup$ @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. $\endgroup$ – Marty Apr 18 '12 at 10:27

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.