GATE CSE 2012 | Question: 39

Question

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

• A. $O (n \log n) $
• B. $ O(n^{2} \log n) $
• C. $ O(n^{2} + \log n) $
• D. $ O(n^{2}) $

Comments

Thank you so much for this. This is how I approaching from the basics and got stuck.

---

Applying 2 by 2 merge

 

---

beautifully clarified sir thnks a lot

Answer 1

We have n words(strings) each of length n. Since both of them are n let's take the length of the word as k(=n). So we have n words each of length k. Comparing 2 words of length k in the worse case will be k comparisons. In the next level, we have words of length 2k each consisting of two words. To compare 2k and 2k words at worse we can have k+k+k =3k(2k+2k-k) comparisons. In the next level we have 7k(4k+4k-k) comparisons, in the next level we have 15k comparisons and so on. The depth of the recursion will be logn.

​​​​​​​

Answer 2

We have to sort Lexicographically.
First we will sort based on 1^st character of each string.
This will take O(nlogn) time as there are n Strings in total (thus ‘n’ number of 1^st characters)

In the Worst Case  i.e. the situation like abbcd, abbcf, abbcb , abbce, abbca

Here we have 5 strings of 5 characters each.

Each string has all first 4 characters same, therefore we have to sort based on last digit here

Now O(nlogn) was for 1^st character of strings, Similarly we will sort 2, 3, 4, …. n times (here n is for sorting based on last digit)

So, n * O(nlogn) = O(n^2 logn)

Option B is correct.