UTpaper

Free mock tests & test series

Question 14Asked in UGC NET Computer Science, November 2017 (Paper II & III, Selected Questions)

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

  1. AO(n log n)
  2. BO(n² log n)
  3. CO(n² + log n)
  4. DO(n³)
Show answerHide answer

Correct answer: (B) O(n² log n)

Explanation

Merge sort performs O(n log n) comparisons, and comparing two strings of length n takes O(n) time in the worst case. So the worst-case running time is O(n · n log n) = O(n² log n).

From UGC NET Computer Science PYQ, November 2017 (Paper II & III, Selected Questions)

This is question 14 of UGC NET Computer Science PYQ, November 2017 (Paper II & III, Selected Questions). See all questions of this paper with answers, or attempt the paper as a timed online test to get your score and all-India rank.