GATE2012-39

10k views

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
1
Hello @Arjun sir, the answer for the above is O(n^2logn) can you pls explain how to solve this question ?
21
[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)
0
thanks alot @sameer2009 for replying.. i got it.
1
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"...
4
3

What should the recursive equation?

I thought that complexity is T(n)= 2T(n/2) + n2. But this gives a complexity of O(n2) using Master's theorem. This complexity turns out to incorrect according to the answers.

0
yes this is that i want....?
–1
O($n^2$) is indeed the correct answer @gmrishikumar

The others have all got it wrong :)

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$

edited
1
nice approach @bhagirathi, plz change the  color from fluorescent green to something else.
2
simple text would suffice the job rather than bedazzling it ;)
3

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.

0
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.. ?
0
Why gate gave marks to all in this question if option B is correct?
0
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?
2
0
There is no nee to add this pharase "Correct me if i am wrong".
0

Since our array is of characters. We need to compare with all the subsequent elements before the placement.

There are logn levels since it is merge sort. For n number of characters we perform n comparisons, so O(n2) time required and it is done in logn levels. So complexity is  O(n2 * logn).

1

@Shaik Masthan @Ayush Upadhyaya is this correct way to approach this problem.

1. There are n list each one having n elements. SO total elements are n^2.

2.Now to make list of size n/2, we will have to compare and move all n^2 elements from one level to other level (merge algo in merge sort).

3. We will have to do this till we get single list. Now when we will get one list? when n/2^k =1 i.e k=logn levels.

So time complexity is work done * number of levels = n^2 * logn.

0
If we use Radix sort with radix = n then the complexity become O(n^2).
0

suppose there are n strings. Now moving one level up in lexicographic order. To compare two strings we need O(n) time. Hence for total of n list it will be n* n/2 = O(n^2) right ?

1

@tusharp-Yes you are correct tushar and your earlier analysis also seems correct.I am sorry I misinterpreted it.

Let us say we have two strings char *a[] ,char *b[] and we want to merge in one list char *c[]

i,j=0;

while(a[i++]==b[j++]); //Almost O(n) comparisons in worst case

if(a[i-1]<b[j-1])//a is lexicographically smaller than b

{ i=0;

while(a[i]!='\0')

c[k++]=a[i++];

j=0;

while(b[j]!='\0')

c[k++]=b[j++];

c[k]='\0';

//a is copied before c in merged string.

And O(n) swaps for each two strings of length n.

}

So, from last level to last-1 level, total comparisons/swaps=$n \times \frac{n}{2}=O(n^2)$

This will be same story for each level.

How many levels?

Untill $\frac{n}{2^l}=1$

$l=log_2n$

Hence total TC-$O(n^2log_2n)$

0
Thank you.
0
what does this lexicographical order mean here ???

It has any effect on no. of comparisons ??
0
Lexicographic order means dictionary order...
yes we have to consider worst case number of comparisons between two lists...
0
 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 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)


2

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

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)

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

0
Pls give me example i am trying my best to understand this ...

S1= ABC.     S2= EFD
How to proceede
0

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)

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
1 vote
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
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
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)

Related questions

1
8.8k views
Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices $S$ and $T$. Which one will be reported by Dijkstra’s shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex $v$ is updated only when a strictly shorter path to $v$ is discovered. $\text{SDT}$ $\text{SBDT}$ $\text{SACDT}$ $\text{SACET}$
Let $G$ be a weighted graph with edge weights greater than one and $G'$ be the graph constructed by squaring the weights of edges in $G$. Let $T$ and $T'$ be the minimum spanning trees of $G$ and $G'$, respectively, with total weights $t$ and $t'$ ... $T' = T$ with total weight $t' < t^2$ $T' \neq T$ but total weight $t' = t^2$ None of the above
Let $W(n)$ and $A(n)$ denote respectively, the worst case and average case running time of an algorithm executed on an input of size $n$. Which of the following is ALWAYS TRUE? $A(n) = \Omega (W(n))$ $A(n) = \Theta (W(n))$ $A(n) = \text{O} (W(n))$ $A(n) = \text{o} (W(n))$
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 (n) = 2T(n/2) + 1$ $T (n) = 2T(n − 1) + 1$