int Fiction( A:: array, n:: integer) {

if (n>1) {

B <- A[1],...,A[n/3]; // copy 1st "third" of A to B

C <- A[n/3+1],...,A[2*n/3]; // copy 2nd "third" of A to C

D <- A[2*n/3+1],...,A[n]; // copy 3rd "third" of A to D

C <- Perturb(C);

cond2 <- Fiction(C, n/3);

if (cond2) {

cond1 <- Fiction(B, n/3);

cond3 <- Fiction(D, n/3);

cond2 <- (cond1 + cond3)/2;

}

return cond2;

}

else

return 1;

}

(a) What is the worst case complexity of this algorithm assuming that the algorithm Perturb when applied to an array of length n has running time complexity (n log(n))? To justify your answer provide and solve a divide-and-conquer recurrence for this algorithm. You may assume that n is a power of 3.

(b) What is the \best case" complexity of this algorithm under the same assumptions as in (a)