24,000 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})$

Hello @Arjun sir, the answer for the above is O(n^2logn) can you pls explain how to solve this question ?
 In merge sort of array of length "n" you get a tree of height log(n).

 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.

 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.

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

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.

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

The others have all got it wrong :)

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

edited

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.

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$

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


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

by

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

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)