Problem:
Question 1: Solve the following recurrence relation by given the running time in terms of asymtotic relation.
T(n) = 2T(n/3) + T(2n/3 ) + Cn.
Question 2: Show the various steps involved in the quick sorting of (1,3,4,-5,9,2,6,5,3).
Question 3: Suggest how you can force the quick sort algorithm to run in O(n log n) time in the worst case.
Please show your work...