Log In
44 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

  1. $O (n \log n) $
  2. $ O(n^{2} \log n) $
  3. $ O(n^{2} + \log n) $
  4. $ O(n^{2}) $
in Algorithms
edited by
Hello @Arjun sir, the answer for the above is O(n^2logn) can you pls explain how to solve this question ?
[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)
thanks alot @sameer2009 for replying.. i got it.
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"...

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.

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

The others have all got it wrong :)

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

11 Answers

0 votes
merge sort take $mlogm$

total no.=n*n


m=no. of elemets

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

mlogm=n^{2}logn^{2} =2*n^{2}logn$$
0 votes

Hope this helps:)

0 votes
Actually you can think of it as:


Work done will be to merge two strings of $\frac{n^{2}}{2}$.

With condition T(n)=1, because strings of length ‘n’ are already sorted.

Now it is pretty straight forward. $O(n^{2}logn)$

Related questions

46 votes
8 answers
Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices $S$ and $T$. Which one will be reported by Dijkstra’s shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex $v$ is updated only when a strictly shorter path to $v$ is discovered. $\text{SDT}$ $\text{SBDT}$ $\text{SACDT}$ $\text{SACET}$
asked Sep 26, 2014 in Algorithms gatecse 11.9k views
43 votes
4 answers
Let $G$ be a weighted graph with edge weights greater than one and $G'$ be the graph constructed by squaring the weights of edges in $G$. Let $T$ and $T'$ be the minimum spanning trees of $G$ and $G'$, respectively, with total weights $t$ and $t'$ ... $T' = T$ with total weight $t' < t^2$ $T' \neq T$ but total weight $t' = t^2$ None of the above
asked Sep 15, 2014 in Algorithms gatecse 8.2k views
31 votes
5 answers
Let $W(n) $ and $A(n)$ denote respectively, the worst case and average case running time of an algorithm executed on an input of size $n$. Which of the following is ALWAYS TRUE? $A(n) = \Omega (W(n))$ $A(n) = \Theta (W(n))$ $A(n) = \text{O} (W(n))$ $A(n) = \text{o} (W(n))$
asked Aug 5, 2014 in Algorithms gatecse 6.8k views
31 votes
4 answers
The recurrence relation capturing the optimal execution time of the $Towers \ of \ Hanoi$ problem with $n$ discs is $T(n) = 2T(n − 2) + 2$ $T (n) = 2T(n − 1) + n$ $T (n) = 2T(n/2) + 1$ $T (n) = 2T(n − 1) + 1$
asked Aug 5, 2014 in Algorithms gatecse 6.1k views