# Good reference for average-case runtime analysis of QuickSort

I'm a beginner in programming with little knowledge about the technicalities. I'm assigned to do a "reading project" on the average case analysis of quicksort. I mean I have to present it in class. Now, I need a good source from which I can read it and find the materials which I can include in my presentation. As for my existing knowledge on algorithms, one can assume that I almost know nothing except for "just codes" and nothing at all about their analysis. Any book or materials having rigorous proofs will also do. Any help will be greatly appreciated!

• Unfortunately you cannot present such an analysis in full detail without a basic grasp of probability theory. You can do some handwaving which might be good enough for your class. There are many online sources on the average case analysis of quicksort, and you should be able to find something that fits your background. Dec 21, 2017 at 18:08
• Thanks for the reply.Well I'm a statistics student, so probability( and required math) hopefully won't pose much of a problem! Maybe you can update your suggestion then? Dec 21, 2017 at 18:24
• Have you tried using your favorite search engine for an average case analysis of quicksort? You can find this analysis in many online lecture notes. Dec 21, 2017 at 18:26
• Check out Sedgewick's books.
– Raphael
Dec 21, 2017 at 18:40

## 1 Answer

Given your stats background, you will find the "indicator variable" analysis easier than the solution via recurrence equations. It is based on computing the probability that two elements of given ranks are compared to each other.

The idea is described on the wikipedia page and in more detail in Section 7.4 of Cormen et al. Introduction to Algorithms 3rd edition.