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

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)