A list of \(n\) strings, each of length \(n\), is sorted into lexicographic…

PYQ GATE 2012Modified — slightly modified from the official paper; see the solution

A list of nn strings, each of length nn, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is

Use standard merge sort with each string comparison scanning characters afresh from the beginning, at unit cost per character comparison. Choose the tightest listed worst-case bound.

  1. A.

    O(n log n)O (n \ log \ n)

  2. B.

    O(n2log⁡ n)O (n^2 \log \ n)

  3. C.

    O(n2+log n)O (n^2 + log \ n)

  4. D.

    O(n2)O (n^2)

Attempted by 847 students.

Sign up free to check your answer

Sign up free

Explore the full course: Algorithms

Loading lesson…