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. 0(n log n)
• B. 0($n^2$ + log n)
• C. 0($n^2$)
• D. 0($n^2$ log n)

Answer 1

The correct option is D 0($n^2$ log n)

The recurrence tree for merge sort will have height n and 0(n${}^2$) work will be done at each level of the recurrence tree (Each level involves n comparisons and a comparison takes 0(n) time in worst case). So time complexity of this merge sort will be 0(n${}^2$ log n) .