According to this lecture http://web.stanford.edu/class/archive/cs/cs161/cs161.1138/lectures/10/Small10.pdf, slide 26, the expected number of comparisons done by quicksort is smaller or equal to $$2n\sum_{k=1}^{n} \frac{1}{k}$$ but I have been taught in class that the expected number of comparisons is equal to $$2\sum_{k=1}^{n-1} \frac{n-k}{k}$$ Could someone tell me where this is derived from? I know that each comparison has probability $\frac{2}{j-i+1}$, for some two numbers $i$ and $j$, as stated in the slides.


$$ \sum_{i=1}^n\sum_{j=i+1}^n\frac1{j-i+1}=\sum_{i=1}^n\sum_{k=1}^{n-i}\frac1{k+1}=\sum_{k=1}^{n-1}\sum_{i=1}^{n-k}\frac1{k+1}=\sum_{k=1}^{n-1}\frac{n-k}{k+1}\;. $$

This gives the right result for $n=2$, so it seems that the denominator of the expression you were given in class is off by $1$.

| cite | improve this answer | |
  • $\begingroup$ sorry, but what happened to the factor of $2$ in the front? $\endgroup$ – gametheorybeginner Mar 21 '16 at 7:57
  • $\begingroup$ @gametheorybeginner: I left it out to reduce the clutter so you can concentrate on the manipulation of the sums :-) $\endgroup$ – joriki Mar 21 '16 at 7:58
  • 1
    $\begingroup$ oh right, I see it now. Thank you. I will ask my professor later about the denominator. $\endgroup$ – gametheorybeginner Mar 21 '16 at 7:58

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.