Correct Answer - Option 2 : O(n
2 log n)
The correct answer is "option 2".
CONCEPT:
The Recurrence relation for the number of comparisons needed to sort an array of n integers is:
T(n) = 2T(n/2) + n
= O(nlog2n)
EXPLANATION:
Consider n strings of length n in place of each integer, since each integer takes O(1) time to sort then,
Complexity to sort one string of size n - O(n)
Complexity to sort n strings of size n - O(n * nlog2n) = O(n2log2n)
Hence, worst case running time is O(n2log2n).