Problem Detail: 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 __________.
- $O(n log n)$
- $O(n^2 log n)$
- $O(n^2 +log n)$
- $O(n^2)$
My attempt: If we are used in-place merge sort , then time complexity for the worst case $Θ(n^2)$ . so none option is correct , since for worst case $O$ are used but not $Θ$ . This question was from competitive exam GATE (see-Q.no.-39) , and answer key is given by GATE “Marks to all(means there is no option correct)” (see-set-A-Q.no.-39) .
Asked By : Mithlesh Upadhyay
Answered By : Tom van der Zanden
(2) is the only correct answer. Merge sort makes $Theta(n log n)$ comparisons. Here, we are comparing strings of length $n$, and comparing two length-$n$ strings takes $Theta(n)$ time in the worst case. Therefore, the running time is $O(n^2 log n)$. It is easy to arrange a set of inputs that makes Merge sort take this long. For instance, consider an input that contains $n$ identical strings; or $n$ strings that all start with the same common prefix (where this common prefix has length $n/2$, say). Then each comparison will take $Theta(n)$ time, and Merge sort will do $Theta(n log n)$ comparisons, for a total of $Theta(n^2 log n)$ running time. Consequently, (2) is correct, and none of the other answers are correct. Your reasoning is incorrect. In general, merge sort makes $Theta(nlog n)$ comparisons, and runs in $Theta(n log n)$ time if each comparison can be done in $O(1)$ time. Therefore, if for some reason we were promised that comparing two strings could be done $O(1)$, all the options would be correct: they would all give an upper bound on the running time of merge sort. $O$ is used to give upper bounds, so $O(n^2)$ is also a correct upper bound for any algorithm whose running time is $O(n log n)$ (since $nlog n leq n^2$). In this case, the problem statement didn’t make that promise, and in the worst case comparing two strings can take $Theta(n)$ time, so answers (1), (3), and (4) are not correct. There’s an important difference between $O$-notation, $Theta$-notation, and $Omega$-notation; they are not equivalent. The problem statement doesn’t say anything about in-place merge-sort, so I’m not sure why you’re bringing that up in your answer. That seems irrelevant. Anyway, while the standard merge sort algorithm is not in-place, there exist ways to do in-place merge-sort with the same asymptotic running time as the standard merge sort algorithm.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/47771
