Consider the following function that takes as input a sequence A

Consider the following function that takes as input a sequence A of integers with n elements, A[1], A[2], . . . , A[n] and an integer k and returns an integer value. The function length(S) returns the length of sequence S.

function mystery(A, k){
n = length(A);
if (k > n) return A[n]; 
v = A[1];
AL = [ A[j] : 1 <= j <= n, A[j] < v ]; // AL has elements < v in A 
Av = [ A[j] : 1 <= j <= n, A[j] == v ]; // Av has elements = v in A
AR = [ A[j] : 1 <= j <= n, A[j] > v ]; // AR has elements > v in A 
if (length(AL) >= k) return mystery(AL,k); 
if (length(AL) + length(Av) >= k) return v;
return mystery(AR, k - (length(AL) + length(Av)));
}

What is the worst-case complexity of this algorithm in terms of the length of the input sequence A?

(A) O(n)
(B) O(n log n)
(C) O(n2)
(D) O(n2log n)

Answer: C
mystery(A, k) finds the k th element in A in ascending order. This is a divide-andconquer selection algorithm, similar to quicksort.
The worst case complexity is O(n 2 ) because of the fixed choice of pivot, as in quicksort.

0Comment