7.7k 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})$

edited | 7.7k views
+1
Hello @Arjun sir, the answer for the above is O(n^2logn) can you pls explain how to solve this question ?
+19
[1] In merge sort of array of length "n" you get a tree of height log(n).

[2] If single element of array is just an integer then at any level of tree, in worst case there will be n comparisons in merge process.

[3] Now if the single element of array is itself an array of size "m" then in order to find larger of 2 elements you need to compare all the m elements.

[4] So at any any level there are n comparisons and each comparison costs "m", so total nmlog(n)
0
thanks alot @sameer2009 for replying.. i got it.
+1
In general merge sort contains "n" elements with "log n"levels and in each level "n" data movements so TC is "n logn"

-->here we have "n" strings each of length"n"and each level we have n*n data movementa so "n^2 logn"...
+3
+3

What should the recursive equation?

I thought that complexity is T(n)= 2T(n/2) + n2. But this gives a complexity of O(n2) using Master's theorem. This complexity turns out to incorrect according to the answers.

0
yes this is that i want....?
–1
O($n^2$) is indeed the correct answer @gmrishikumar

The others have all got it wrong :)

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$\$
by Active (1.6k points)