Consider the Stooge-sort algorithm, shown in Algorithm 11.5, and suppose we change the assignment statement for m (on line 6) to the following: 

m ← max{1, [n/4]} 

Characterize the running time, T(n), in this case, using a recurrence equation, and use the master theorem to determine an asymptotic bound for T(n). 

Algorithm 11.5

Transcribed Image Text:

Algorithm StoogeSort(A, i, j): Input: An array, A, and two indices, i and j, such that 1 < i A[j] then Swap A[i] and A[j] else if n > 2 then m - [n/3] StoogeSort(A, i, j – m) StoogeSort(A, i+m, j) StoogeSort(A, i, j – m) // Sort the first part // Sort the last part // Sort the first part again | return A Algorithm 11.5: Stooge-sort.