A list of \(n\) strings, each of length \(n\), is sorted into lexicographic…
2012
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)\)
Attempted by 287 students.
Show answer & explanation
Correct answer: B
Answer: O(n^2 log n)
Reasoning:
There are n strings to sort, so a comparison-based sorting algorithm like merge sort performs O(n log n) comparisons in the worst case.
Each comparison between two strings of length n can require inspecting up to n characters, so a single comparison costs O(n) time in the worst case.
Multiply the number of comparisons by the cost per comparison: O(n log n) × O(n) = O(n^2 log n).
Therefore the worst-case running time for sorting n strings of length n with merge sort is O(n^2 log n).