Question

A list of n strings, each of length n, is sorted into lexicographic order using merge - sort algorithm. The worst case running time of this computation is:
1. O(n log n)
2. O(n² log n)
3. O(n² + log n)
4. O(n³)

Answer 1

Correct Answer - Option 2 : O(n² 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(nlog₂n)

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 * nlog₂n) = O(n²log₂n)

Hence, worst case running time is O(n2log2n).