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


closed as unclear what you're asking by Raphael Oct 1 '15 at 16:07

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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$ – 1 0 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.