Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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 1

up vote 0 down vote accepted

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

share|improve this answer
    
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 –  Bidit Acharya 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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.