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 UNUSUSAL.

CRUEL A 1 n if n >1 RUEL n/2]) CRUEL(ACn/2 +1.. n]) UNUSUAL 1... n UNUSUAL 1..n if n 2 if A[1] A12] (the only comparison!) swap A[1] AC2] else (swap 2nd and 3rd quarters) for i 1 to n/4 swap Ali n/4] Ali n/2] UNUSUAL GAL1 n/2]) recurse on left half UNUSUAL CAIn/2 1.. n]) (recurse on right half)) UNUSUAL 1..3n/4]) recurse on middle half