Consider the following algorithm prototype in pseudocode, how to get the best case time complexity?:

Question:

What is the best 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)?

And you may assume that n is a power of 3.

Note that all logarithms in this assignment are base 2, i.e. log f(n) log2 f(n).

int Fiction( A:: array, n:: integer) if (n>1) // copy 1st "third" of A toB C A[n/3+1],.. ..A[2*n/3]; // copy 2nd "third" of A to C D