A list of n strings, each of length n, is sorted into lexicographic order…
2017
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 :
- A.
O(n log n)
- B.
O(n2 log n)
- C.
O(n2 + log n)
- D.
O(n3)
Attempted by 534 students.
Show answer & explanation
Correct answer: B
Answer: O(n^2 log n)
Reasoning:
Merge sort performs Θ(n log n) comparisons of elements when sorting n items.
Each comparison between two strings of length n can take Θ(n) time in the worst case (for example, when the strings share long common prefixes so many characters must be checked).
Multiply the number of comparisons by the cost per comparison: Θ(n log n) · Θ(n) = Θ(n^2 log n).
Therefore, the worst-case running time to sort n strings of length n using merge sort is Θ(n^2 log n).
A video solution is available for this question — log in and enroll to watch it.