Consider an algorithm UNBALANCEDSORT identical to MERGESORT except that, instead of dividing an array of size...

Transcribed Image Text:

Consider an algorithm UNBALANCEDSORT identical to MERGESORT except that, instead of dividing an array of size n into two arrays of size n/2 to recursively divide into two arrays with sizes roughly n/3 and 2n/3. For simplicity, assume that n is always divisible by divisors (i.e. you may ignore floors and ceilings) (a) (1 point) Write down a recurrence relation for UNBALANCEDSORT. Assume that merging takes e(n) time. (b) (1 point) Solve the recurrence (assuming that T(1) = O(1)) to show that T(n) = O(n lgn). (c) (1 point) Suppose that UNBALANCEDSORT is instead divided into two arrays of size n/4 and 3n/4. How does the asymptotic runtime of the algorithm change? What about dividing into n/a and (a 1)n/a for arbitrary constant 1 Consider an algorithm UNBALANCEDSORT identical to MERGESORT except that, instead of dividing an array of size n into two arrays of size n/2 to recursively divide into two arrays with sizes roughly n/3 and 2n/3. For simplicity, assume that n is always divisible by divisors (i.e. you may ignore floors and ceilings) (a) (1 point) Write down a recurrence relation for UNBALANCEDSORT. Assume that merging takes e(n) time. (b) (1 point) Solve the recurrence (assuming that T(1) = O(1)) to show that T(n) = O(n lgn). (c) (1 point) Suppose that UNBALANCEDSORT is instead divided into two arrays of size n/4 and 3n/4. How does the asymptotic runtime of the algorithm change? What about dividing into n/a and (a 1)n/a for arbitrary constant 1