I found this link: http://theory.stanford.edu/~tim/w11/l/qsort.pdf and it kind of theoretically describes how to approach finding expectation for the number of comparisons in a Quicksort.

Using this, how would I find and prove the expectation for an array of a concrete number of items, for example 5? (see the formula in the second section of the link) Would my expectation be !https://i.imgur.com/7BIE3qj.png)! but replace the n by 5 for example (to get the expected number of comparisons for a 5 length array)

the second formula reads: !(https://i.imgur.com/66gvyjp.png)!

I understand I should just replcae the n with for example 5 if I want to find the number of comparisons expected for a concrete array, however I don't think I quite understand how the proof would apply in this case, however. I was wondering if anyone knew an easier proof for finding the expected number of comparisons in a randomized quicksort for an array of length n.

  • $\begingroup$ You should consider clarifying the body of your question(with the help of the link you've added). It is unclearly exactly what you are trying to ask here. $\endgroup$ – LastIronStar Nov 13 '17 at 20:53
  • $\begingroup$ @LastIronStar done $\endgroup$ – Lola1984 Nov 13 '17 at 21:06
  • 1
    $\begingroup$ Did you try writing down the series term-wise for $\mathbb{E}[C]$ using $n=5$(first part of second formula)? $\endgroup$ – LastIronStar Nov 13 '17 at 21:13
  • $\begingroup$ I am not really sure how this formula was actually derived in the first place, which is why I don't feel comfortable using it. $\endgroup$ – Lola1984 Nov 13 '17 at 22:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.