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.

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
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)
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
Actually you can think of it as:

$T(n^{2})=2T(\frac{n^{2}}{2})+n^{2}$

Work done will be to merge two strings of $\frac{n^{2}}{2}$.

With condition T(n)=1, because strings of length ‘n’ are already sorted.

Now it is pretty straight forward. $O(n^{2}logn)$
by