Discuss the following problem:
Q: 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 n-1 i=0ΣT(i) +T(n-1-i),T(0)= 0.
(a) Let S(n) = n-1 i=0Σ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, ..., 12.
(c) What are the time and space requirements for computing T(n)?