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 in O(n log n) for n elements. - When sorting n strings of length n, each comparison between two strings takes O(n) due to the length of the strings. - Thus, the total time complexity becomes: O(n · n log n) = O(n2 log n).