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.

  • 0
    thanks for the responses. if anyone wants to leave an answer i'll accept it.2012-02-15

1 Answers 1

0

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

  • 0
    @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.2012-04-18