Thread: Average case complexity

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?

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.