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

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

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)

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.