Consider the following pseudocode for a sorting algorithm, for 0 1. badSort(A[0 ...n 1)) if...

Transcribed Image Text:

Consider the following pseudocode for a sorting algorithm, for 0 <a<1 and n > 1. badSort(A[0 ...n – 1)) if (n = 2) and (A[0] > A[1]) swap A[0] and A[1] else if (n > 2) = [a n] badSort(A[0. m - 1]) badSort(A[n - m.n - 1]) .. m – 1]) a. Show that the divide and conquer approach of badSort fails to sort the input array if a < 1/2. b. Does badSort work correctly if a = 3/4? If not, why? Explain how you fix it. c. State a recurrence (in terms of n and a) for the number of comparisons performed by badSort. d. Let a = 2/3, and solve the recurrence to determine the asymptotic time complexity of badSort. Consider the following pseudocode for a sorting algorithm, for 0 <a<1 and n > 1. badSort(A[0 ...n – 1)) if (n = 2) and (A[0] > A[1]) swap A[0] and A[1] else if (n > 2) = [a n] badSort(A[0. m - 1]) badSort(A[n - m.n - 1]) .. m – 1]) a. Show that the divide and conquer approach of badSort fails to sort the input array if a < 1/2. b. Does badSort work correctly if a = 3/4? If not, why? Explain how you fix it. c. State a recurrence (in terms of n and a) for the number of comparisons performed by badSort. d. Let a = 2/3, and solve the recurrence to determine the asymptotic time complexity of badSort.