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

Actually you can think of it as:

$T(n^{2})=2T(\frac{n^{2}}{2})+n^{2}$
 

Work done will be to merge two strings of $\frac{n^{2}}{2}$.

With condition T(n)=1, because strings of length ‘n’ are already sorted.

Now it is pretty straight forward. $O(n^{2}logn)$

Answer 2

Hope this helps
the key concept  was element here is " n length string " (but in merge sort we studied element was a 1 length entity)

 This is how the recurrence relation will be:-

 

 

Answer 3

Since worst case time complexity of merge sort is O(nlogn) for a given string of length n. For n such strings we have to run an iterative loop n times,one for each performing worst case merge sort on a single string. So, complexity is given as O(n*nlogn)=O(n2logn)

Answer 4

merge sort take $mlogm$

total no.=n*n

           =n^{2}.

m=no. of elemets

n^{2}logn^{2}$total no.=n*n=n^{2}.

mlogm=n^{2}logn^{2} =2*n^{2}logn$$