Printable View
Looks like this question has been asked before, but I am not able to find an answer to it so I will ask again.
How do you compute the complexity of an algorithm in an average case? I can (barely) understand why Quicksort has O(n^2) in worst case, but I cannot figure out why it has O(nlogn) in an average case. Thanks so much.
I'll take a stab and say that it has to do with the fact that the sum of the number of items from the smaller half of each partition step follows the normal distribution. (Assuming say a random splitter choosing technique)
At one end of the bell curve lies the chance of hitting the worst possible case with zero items in the smaller half every time. At the other end of the bell curve we have the case where the halves are equal every time.
Somewhere near the middle of the bell curve you get approximately a 1/3rd 2/3rd split on average, and the most likely cases are around there. That case is O(n * log n)
Does that make sense to you?
Thanks a lot iMalc. I manage to understand until where you mention the most likely cases are around the 1/3rd 2/3rd split on average, which I also understand, but how does one compute that that case is O(nlogn)? If this is derived according to some Math theories than I will have to dig up my university text books. Cheers.
I'll assume you can see how the perfect case of equal items on each side every time is O(n * log n). If not, let me know.
The maximum recursion depth for such a case is ceil(log base 2 of n). I.e. Log base 2 of 1000 is 9.9657 which we round up to 10.
Now if you get about a 1/3rd 2/3rd split then the maximum recursion depth should be within a constant factor of the perfect case. I can't think of an easy way to show why that is at the moment. In that case the constant factor might be about 2, meaning that the expected maximum recursion depth might be around 20.
In Big-Oh notation we simply ignore that constant factor.
Note that I'm not even sure that a 1/3rd 2/3rd split is exactly the average case, but that is not important. For all I know the actual average case might involve the golden ratio or whatever..., but basically the average case will involve only a constant factor times the maximum recursion depth of the perfect case.
Thanks again for the explanations iMalc. This is complicated, but I think I understand now. Cheers!