Sorting n strings using Merge sort

Question

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?

I searched this question and everywhere I found the answer to be: O(n²logn).

While my approach is as follows:
Comparing two strings require O(n) comparisons, hence each merge will take O(n²) time.
So, the recurrence equation will be:
T(n) = 2T(n/2) + O(n²)
Therefore, by Master Method:
T(n) = O(n²).

Correct me where I am wrong.

Answer 1

arunk2's answer is correct, but here are some more details of exactly where the recurrence is going wrong:

In normal merge sort of numbers, the recurrence is: T(n) = 2T(n/2) + cn ; where c is some constant

Notice what happens while solving this recurrence, and the difference while solving the recurrence T'(n) with c(n^2)

T(n) = 2T(n/2) + cn

T(n) = 2[2T(n/(2^2)) + c(n/2)] + cn

T(n) = (2^2)T(n/(2^2)) + cn + cn //after logn steps, 'cn' will be added logn times, therefore resulting in O(nlogn)

---

T'(n) = 2T(n/2) + c(n^2)

T'(n) = 2[2T(n/(2^2)) + c((n/2)^2)] + c(n^2)

T'(n) = (2^2)T(n/(2^2)) + c(n^2)/2 + c(n^2) //every time n^2 is halving, which results in O(n^2)

If you analyze the algorithm closely, (and as mentioned in arun's answer), the work done at each level is always n^2, and it doesn't halve at each level, and that's why the time complexity is O((n^2)logn) instead of simply O(n^2) by masters theorem.

Answer 2

Your analysis and reduction is correct. But the problem is in the interpretation of recurrence equation of master theorem.

T(n) = 2T(n/2) + O(n²)

The n in the equation represents no.of elements in the list to be sorted. The O(n²) is not entirely correct. It is O(n * n-character comparisons). This will be evident if we substitute 'n-character comparisons' operations with a different complexity, which is independent of no.of elements. Let it be O(m). Then we have

T(n) = 2T(n/2) + O(n * m)

we have a = 2, b = 2, c = 1 and c = Log_ba (case 2)

Hence, T(n) = O(n * m * log n)

Now, substituting m with n

T(n) = O(n² * log n)

We can also justify this as - the recurrence tree for merge sort will have height Log(n). O(n²) work will be done at each level of the recurrence tree in merge operation.

Hence, a total of O (n² log n)

Hope it helps!

Answer 3

I think that your conclusion of O(n^2*lgn) is correct. If you were dealing with a set of n numbers, we know that mergesort would require O(nlgn). The difference here is that we are now dealing with strings, each of which is n long. The only impact on the mergesort algorithm would be the comparison of two strings in the base case. Instead of an O(1) comparison of two numbers, we would instead have to compare the two strings. In the general case, this is an O(n) operation, because we might have to walk down each of the two length n strings.