Explore BrainMass
Share

Explore BrainMass

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

    © BrainMass Inc. brainmass.com October 10, 2019, 4:37 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