Question

What is the average performance of Quicksort assuming every input permutation is equally likely? Prove it.

Hint: In this case pivot(split) element very likely to provide good balance during partition.

Answer 1

Let T(n) be the time needed for n input.

Pivot position i(belongs to) {0,1,2,...,n-1}

Let time for partitioning is kn (k is constant)

Let the pivot position be i then we can partition the array into 2 subarrays, one containing i elements and n-1-i elements

Average run time

         

.......(1)

Again using the recurrence relation we have

......(2)

Subtracting (1)-(2)

Therefore

Dividing by n(n+1)

Using this we write

........

_______________________________________

(Adding all these)

                              H_n is the nth harmonic number   

                

Thus