Consider the following pseudocode for a sorting algorithm, for 0 < < 1 and n >
Fantastic news! We've Found the answer you've been seeking!
Question:
Consider the following pseudocode for a sorting algorithm, for 0 < α < 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)
m = [α*n]
badSort(A[0... m-1])
badSort(A[n-m... n-1])
badSort(A[0...m-1])
4a. Show that the divide and conquer approach of badSort fails to sort the input array if α ≤ 1/2.
4b. Does badSort work correctly if α = 3/4? If not, why? Explain how you fix it.
4c. State a recurrence (in terms of n and α) for the number of comparisons performed by badSort.
4d. Let α= 2/3, and solve the recurrence to determine the asymptotic time complexity of badSort.
Related Book For
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
Posted Date: