Question

A list of n strings, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst-case running time of this computation is:

• A. O(n log n)
• B. O(n^2 log n)
• C. O(n^2 + log n)
• D. O(n^2)

Hint:

Combine the sorting algorithm complexity with the cost of comparisons for string-based sorting problems.

Answer 1

The Correct Option is B

Merge sort operates with a time complexity of O(n log n) for n elements. When sorting n strings, each of length n, a single comparison takes O(n) due to string length. Therefore, the total time complexity becomes O(n · n log n) = O(n2 log n).