GATE CS 2012 Q.39 (CS Q.39): Searching and Sorting Algorithms

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

Official answer and solution

Official answer: Marks to all
From: Official GATE 2012 answer key

Why the marks went to every candidate

Official GATE answer key awarded Marks to All for this question.

Solution

Multiply the number of comparison operations in Merge Sort by the character comparison cost between strings of length n.

Standard merge sort on a list of $n$ elements makes at most $O(n \log n)$ element comparisons in the worst case.
Comparing two strings of length $n$ to establish lexicographic order takes $O(n)$ character comparisons in the worst case (when they share a long common prefix).
Multiplying the number of element comparisons by the time required per comparison gives:

\text{Total running time} = O(n \log n) \times O(n) = O(n^2 \log n)

Reason for Marks to All: Standard big- $O$ represents an asymptotic upper bound. Although $\Theta(n^2 \log n)$ is the tight bound corresponding to option (B), differing conventions regarding whether $n$ in the options referred to string length or total input size prompted GATE to award Marks to All.

Final answer

Marks to All (Tight worst-case complexity is O(n^2 log n), Option B; full credit given to all candidates).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2012 Computer Science and Information Technology (CS)
Question: 39 of 65, printed as CS Q.39
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source