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

Dark Mode

24,000 views

57 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

- $O (n \log n) $
- $ O(n^{2} \log n) $
- $ O(n^{2} + \log n) $
- $ O(n^{2}) $

edited
Aug 17, 2022
by Deepak Poonia

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

19

7 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

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

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