Multiple choice

A list of n stings, 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(nlogn)

  2. O(n2 logn)

  3. O(n2 +logn)

  4. O(n2)
Reveal answer Fill a bubble to check yourself
B Correct answer
Explanation

The height of the recursion tree using merge sort is logn and n2 comparisons are done at each level, where at most n pairs of strings are compared at each level and n comparisons are required to compare any two strings, So the worst case running time is O(n2 logn)

Keep practicing — related questions