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