Explore BrainMass
Share

Recurrence equations for Quicksort

This content was STOLEN from BrainMass.com - View the original, and get the 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)?

© BrainMass Inc. brainmass.com September 19, 2018, 1:32 am ad1c9bdddf - https://brainmass.com/computer-science/arrays/469400

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