[Solved]: A list of n strings lexicographic order using the merge-sort algorithm. The worst case running time of this computation is

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 __________.

1. $O(n log n)$
2. $O(n^2 log n)$
3. $O(n^2 +log n)$
4. $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(n\log 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 $n\log 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