Question

Derive the recurrence for the average time complexity of Quick Sort.

Answer 1

`Hey,

Note: Brother if you have any queries related the answer please do comment. I would be very happy to resolve all your queries.

The average case run time of Quick sort is O(nlogn).

• Assume a strategy for choosing pivots such that, after partitioning A into A1 and A2, all lengths of A1 from 0 to |A|-1 are equally likely.

• The running time of quickSort equals the time of its two recursive calls plus time to do the partition.

  • pivot index is O(last-first).

  Suppose that we partition n elements into sub-arrays of length i and (n-i).

Time T to sort the n elements is then:

T(n)=T(i)+T(n-i)+c⋅n

• This kind of formula is called a recurrence relation. They are very common in describing the performance of recursive routines.

Because i is equally likely to be any value from 0 to n-1, the average (expected) value of T(i) is

E(T(i))=1n∑j=0n-1T(j)

Since n-i can take on the same values as i, and all such values are equally likely,

E(T(n-i))=E(T(i))

On average, then

T(n)=2n(∑j=0n-1T(j))+c⋅n

Multiply through by n:

n⋅T(n)=2⋅(∑j=0n-1T(j))+c⋅n2

n is just a variable, so this must be true no matter what value we plug in for it. Try replacing n by n-1.

(n-1)⋅T(n-1)=2⋅(∑j=0n-2T(j))+c⋅(n-1)2

So now both of these are true:

n⋅T(n)=2⋅(∑j=0n-1T(j))+c⋅n2(n-1)⋅T(n-1)=2⋅(∑j=0n-2T(j))+c⋅(n-1)2

Subtract the 2nd equation from the first:

nT(n)-(n-1)T(n-1)=2T(n-1)+2cn-c

Collect the T(n-1) terms together and drop the -c term:

nT(n)=(n+1)T(n-1)+2cn

Next we apply a standard technique for solving recurrence relations. Divide by n(n+1) and "telescope":

T(n)n+1=T(n-1)n+2cn+1T(n-1)n=T(n-2)n-1+2cnT(n-2)n-1=T(n-3)n-2+2cn-1⋮

Note that most of the terms on the left will have appeared on the right in the previous equation, so if we were to add up all these equations, these terms would appear on both sides and could be dropped:

T(n)n+1=T(1)2+2c∑j=3n+11j

As n gets very large, ∑j=3n+11j approaches ln(n)+γ, where γ is Euler's constant, 0.577...

Hence

T(n)n+1=T(1)2+2c⋅ln(n)+2cγ=ln(n)+c2=O(ln(n))

and so

T(n)=O(n⋅log(n))

Kindly revert for any queries

Thanks.