edited by
28,614 views
71 votes
71 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}) $
edited by

14 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
        else
           {
                 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 votes
1 votes
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
Answer:

Related questions

59 votes
59 votes
5 answers
2
42 votes
42 votes
4 answers
3
35 votes
35 votes
3 answers
4
gatecse asked Aug 5, 2014
15,482 views
The recurrence relation capturing the optimal execution time of the $Towers \ of \ Hanoi$ problem with $n$ discs is$T(n) = 2T(n − 2) + 2$$T (n) = 2T(n − 1) + n$$T (...