The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+25 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}) $
asked in Algorithms by Boss (18.3k points)
edited by | 5.2k views
Hello @Arjun sir, the answer for the above is O(n^2logn) can you pls explain how to solve this question ?
[1] In merge sort of array of length "n" you get a tree of height log(n).

[2] If single element of array is just an integer then at any level of tree, in worst case there will be n comparisons in merge process.

[3] Now if the single element of array is itself an array of size "m" then in order to find larger of 2 elements you need to compare all the m elements.

[4] So at any any level there are n comparisons and each comparison costs "m", so total nmlog(n)
thanks alot @sameer2009 for replying.. i got it.
In general merge sort contains "n" elements with "log n"levels and in each level "n" data movements so TC is "n logn"

-->here we have "n" strings each of length"n"and each level we have n*n data movementa so "n^2 logn"...

5 Answers

+39 votes
Best answer
I thought like this:

you are given the first character of each $n$ strings to sort it will take $O(n \log n)$ the worst case we may have to do the above process $2$ times,$3$ times,........,$n$ times so $n*O(n \log n)=O(n^2 \log n)$ please correct me if my approach is wrong...
answered by Boss (14.3k points)
edited by
nice approach @bhagirathi, plz change the  color from fluorescent green to something else.
simple text would suffice the job rather than bedazzling it ;)

right approach i guess...

want to put in other words like:-

lets take as string has length N (change n to N for some time) 

so first of all we will sort the list of n strings for the first characters of all strings (it will take n log n time).

[something like radix sort] so for second time we will sort for 2nd characters (which also take n log n time) and then for 3rd char. then for 4th and so on till N characters.

In this way it will take N*n lg n or  n*n lg n or  nlg n.
plz correct me wherever i m wrong.

what if  we assign a weight for every string which can be done in O(N^2) time and do merge sort on 'n' weights which will be O(N^2 + NlogN ) = O(N^2) ---> then option will be D ... correct if i'm wrong.. ?
Why gate gave marks to all in this question if option B is correct?
How will this approach work?If we have sorted the first character of each string,now what is next step? We will read the next character from each string ?Then how will this be merged with previous sequence?
+13 votes
**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 (A,P,Q,R)
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)


answered by Boss (12.3k points)
+10 votes
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
answered by Boss (34.8k points)
+4 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
answered by (147 points)
+3 votes

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(n2).

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

answered by Active (2.2k points)
Pls give me example i am trying my best to understand this ...
S1= ABC.     S2= EFD
   How to proceede

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

41,080 questions
47,675 answers
62,393 users