# Average case running time of quick sort

How to show that the quick-sort algorithm runs in $$O(n^m)$$ time on average for some constant $$m < 2$$?

Because on average, the expected running time is in $$O(nlog n)$$. The algorithm should not be in exponential time.