Share
Explore BrainMass

Recurrence equations for Quicksort

The following recurrence equation gives the expected number of comparisons for Quicksort, given that the "pivot element" is selected uniformly at random from the list:

T(n) = (n - 1) + (1/n)* SUM[i=0,n-1](T(i) + T(n-1-i)), T(0) = 0.

(a) Let S(n) = SUM[i=0,n-1](T(i) + T(n-1-i)). Give Dual recurrence equations expressing T(n) in terms of S(n), and S(n) in terms of S(n-1) and T(n-1).

(b) Evaluate S(n) and T(n) for n = 1, 2, ..., 7.

(c) What are the time and space requirements for computing T(n)?

Attachments

Solution Preview

(a) Since the summation expression in the right hand side of T(n) equation is the complete right hand side of S(n) equation, it is straightforward to express T(n) in terms of S(n).

T(n) = (n-1) + (1/n) S(n), T(0) = 0

Expressing S(n) in terms of S(n-1) and T(n-1) is slightly tricky.

S(n-1) = SUM[i=0 to ((n-1) - 1)] (T(i) + T((n-1) -1 -i))
= SUM[i=0 to (n-2)] T(i) + SUM[i=0 to (n-2)] T((n-1) -(1+i))
= (T(n-1) + SUM[i=0 to (n-2)] T(i)) - T(n-1) + SUM[i=0 to (n-2)] T((n-1) -(1+i))
= SUM[i=0 to (n-1)] T(i) - T(n-1) + SUM[i=0 to (n-2)] T((n-1) -(1+i))
= SUM[i=0 to (n-1)] T(i) - T(n-1) + SUM[(j-1)=0 to (n-2)] T((n-1) -(1+(j-1))) -- Substituting i=j-1
= ...

Solution Summary

Solution applies the concept of memoing to compute T(n), and accordingly works out the time and space requirements for computing T(n) in part (c).

$2.19