there is pseudocode for a recursive function called Unusual.

(a) Write down the recurrence relation for the running time of Unusual. You are welcome to ignore floors and ceilings, but make sure you write the base case also, expicitly.

(b) Solve the recurrence using the Master Theorem and find the running time of StoogeSort.

CRUEL 1..n if n> 1 CRUEL(AI 1.. n/2]) CRUELCAIn/2 +1.. n]) UNUSUALCAD 1.. n]) UNUSUAL A 1.. n if n- 2 (the only comparison!) if A[1] A12] swap A[1] A12] else for i 1 to n/4 (swap 2nd and 3rd quarters) swap Ali n/4] Ali +n/2] NUSUAL n/2]) (recurse on left half) (recurse on right half) UNUSUALCAIn/2+1..n]) (recurse on middle half) UNUSUALCALn/4+ 1... 3n/4D