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

Can someone try to obtain the answer using Recurrence relation,I tried but it was giving O(n^2)

---

When we have $n$ elements in array, Merge Sort Makes $\Theta (nlogn)$ Comparisons.

When each element is simply Integer, each comparison takes $\Theta(1)$ time, So Merge Sort time complexity becomes $\Theta(n)$ Comparisons  $\times \Theta(1)$ time per comparison.

So, $\Theta(nlogn)$ time complexity.

When each element is string of length $P$, each comparison takes $O(P)$ time, So Merge Sort time complexity becomes $ \Theta(nlogn)$ Comparisons $\times  O(P)$ time per comparison.
So, $O(P*nlogn)$ time complexity.

For this question $P$ is $n.$

WHY $T(n) = 2T(n/2) + O(n^2)$ is NOT Correct Recurrence Relation for this question??

Answer : Because, in this recurrence relation, one of the $'n'$ in $n^2$ is Not Recurrence variable here.
If you didn't understand this, then assume that each string has length $m.$
Now, Recurrence Relation will be $T(n) = 2T(n/2) + O(mn)$ .. This is correct Recurrence Relation. 

NOTE that $m$ is Not Recurrence variable, So, if we put $m=n$ in this equation, we'll make it Recurrence variable which is Wrong. 

Basically Open the Recursive equation and at the end of series calculation, put $m =n$.

---

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

Answer 1

We are given the first character of each $n$ strings. To sort them, it will take $O(n \log n)$ time. In the worst case we may have to do the above process $2$ times, $3$ times, $\ldots ,n$ times. So, $n*O(n \log n)=O(n^2 \log n).$

Correct Answer: $B$

Comments

what does this lexicographical order mean here ???

It has any effect on no. of comparisons ??

---

Lexicographic order means dictionary order...
yes we have to consider worst case number of comparisons between two lists...

---

	No. of nodes	No. of strings in each node	No. of letter comparisons in the worst case (Comparisons are made from previous level)
First level merge	n/2	2	n + n = 2n
Second level merge	n/4	4	2n + 2n = 4n
Third level merge	n/8	8	4n + 4n = 8n

 

So, at each level we will make n$^{2}$ comparisons. And we need to add these "depth" number of times. (depth = $\log_{2} n$)

Time complexity = n$^{2}$ + n$^{2}$ +n$^{2}$ +.....+ n$^{2}$ (we will have depth=$\log_{2} n$ terms here)

= $O(n^{2}\log_{2} n)$

Answer 2

**answer is O(n^2logn)
  , 
we know Merge sort has recurrence form
T(n) = a T(n/b) + O(n)
in case of merge sort 
it is 
T(n) = 2T(n/2) + O(n) when there are n elements
but here the size of the total is not "n" but "n string of length n"
so a/c to this in every recursion we are breaking the n*n elements in to half
for each recursion as specified by the merge sort algorithm
MERGE-SORT(A,P,R)  ///here A is the array P=1st index=1, R=last index in our case it 
                      is n^2 
if P<R
then Q = lower_ceiling_fun[(P+R)/2]
      MERGE-SORT(A,P,Q)
      MERGE-SORT(A,Q+1,R)
      MERGE (A,P,Q,R)
MERGE(A,P,Q,R) PROCEDURE ON AN N ELEMENT SUBARRAY TAKES TIME O(N)
BUT IN OUR CASE IT IS N*N
SO A/C to this merge sort recurrence equation for this problem becomes
T(N^2)= 2T[(N^2)/2] + O(N^2)
WE CAN PUT K=N^2 ie.. substitute to solve the recurrence
T(K)= 2T(K/2) + O(K)
a/c to master method condition T(N)=A T(N/B) + O(N^d)
                               IF A<=B^d  then T(N)= O(NlogN)
therefore T(K) = O(KlogK)
substituting K=N^2
we get T(N^2)= O(n*nlogn*n)
       ie.. O(2n*nlogn)
         .. O(n*nlogn)

 

Comments

Why is the complexity not T(N)= 2T[N/2] + O(N^2) ?

---

Actually it is:

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

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

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

Answer 3

The worst case complexity of merge sort is O(n log n). Hence the worst case complexity for sorting first letter of n strings will be O(nlog n).

In worst case, we have to sort all n letters in each string.

Hence total complexity will be upto O(n * n log n) = O( n^2 log n)

Answer is B

Answer 4

Lets take a string of length n , we need n comparisons to sort it , and there are n such strings .

now string of length n requires n comparisons , if we have  n such strings , Total time for comparisons will be O(n²).

now imagine that merge sort binary tree.. in that ,at every level O(n²) work is done , and there are Logn such levels therefore total time taken wil be O(n²logn).

Comments

Pls give me example i am trying my best to understand this ...
 
S1= ABC.     S2= EFD
   How to proceede

---

Consider two strings aaa, aab compare letter by letter. In the worst case for two list n comparisons have to be done right, in the case both are same. So for the first level there will be n/2 -> O(n) comparison pairs will be there right 1st list with 2nd , 3rd with 4th so on. So how much time does one pair take - O(n). Total pairs n/2->O(n) so total work done at each level O($n^{2}$) . No of levels - Log n so . Total work done - 

O($n^{2}$logn)