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

  • 1
    $\begingroup$ There is no question here. We don't do homework checking. $\endgroup$ – Raphael Oct 1 '15 at 16:07

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

  • $\begingroup$ rt sir , I was talking about in place merge sort , anyway , here , can we apply out place merge sort ? $\endgroup$ – ً ً Oct 1 '15 at 14:40
  • $\begingroup$ @user4791206 It is possible (albeit more tricky) to sort in-place with mergesort, too. If you want to talk about a specific algorithm, you have give or cite it. $\endgroup$ – Raphael Oct 1 '15 at 16:09
  • $\begingroup$ @Tom van der Zanden Sir what would be the recurrence for this problem? $\endgroup$ – Sumeet Apr 3 '18 at 17:16

Not the answer you're looking for? Browse other questions tagged or ask your own question.