23,416 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.

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)
by
merge sort take $mlogm$

total no.=n*n

=n^{2}.

m=no. of elemets

n^{2}logn^{2}$total no.=n*n=n^{2}. mlogm=n^{2}logn^{2} =2*n^{2}logn$\$

I hope its clear!

We have n words(strings) each of length n. Since both of them are n let's take the length of the word as k(=n). So we have n words each of length k. Comparing 2 words of length k in the worse case will be k comparisons. In the next level, we have words of length 2k each consisting of two words. To compare 2k and 2k words at worse we can have k+k+k =3k(2k+2k-k) comparisons. In the next level we have 7k(4k+4k-k) comparisons, in the next level we have 15k comparisons and so on. The depth of the recursion will be logn.

​​​​​​​