Explore BrainMass
Share

# Recurrence equations for Quicksort

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

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)?

https://brainmass.com/computer-science/arrays/469400

#### 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