in Algorithms edited by
57 votes
57 votes

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

  1. $O (n \log n) $
  2. $ O(n^{2} \log n) $
  3. $ O(n^{2} + \log n) $
  4. $ O(n^{2}) $
in Algorithms edited by


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

edited by

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.

12 Answers

7 votes
7 votes
The function Compare2strings will take input two strings and output the lexicographic order in which they should appear
    compare2strings(String s1, String s2)
         int ptr=0;
         while( s1[ptr] = = s2[ptr]  && ptr < n )
        {     ptr++;
       if(  s1[ptr] < =  s2[ptr]
            return (s1,s2)
       else if(  s1[ptr] >  s2[ptr]
            return (s2,s1)
}             // This function takes worst case O(n) to compare two strings.......
MergeSort(Sequence 1.......nth strings)
       if(Single string is given as input)
             return string
                 MergeSort(Sequence 1,2,3.....n/2th strings)
                 MergeSort(Sequence (n/2+1),(n/2+2).......nth strings)
                 Merge(Sequence 1,2,3.....n/2th strings, Sequence (n/2+1),(n/2+2).......nth strings )
Merge(Seq1 , Seq2)
{    Worst case number of string comparisons among strings = O(n + n-1) = O(n)
      with each comparison O(n) using compare2strings function
    Merge cost in worst case  = O(n).O(n) = O(n^2)
T(n) = 2T(n/2) + O(n^2)
Master theorem   T(n) = O(n^2)  
so B, C, D all are answers. Maybe that is the reason marks are awarded to all
2 votes
2 votes
Every list have n element, total n list, then total element =n*n=n^2 Merge sort apply : n^2logn^2 => 2n^2logn => O(n^2logn)
1 vote
1 vote
For two strings to sort their element total n^2 comparisons will be there in this case, so recurrence would be

T(n^2) = 2 T(n^2/2) + O(n^2)

which gives time complexity as n^2logn
1 vote
1 vote
Actually you can think of it as:


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)$

Related questions