5
$\begingroup$

A list of n strings each of length n is being sorted in lexicographical order using the merge sort algorithm. Since we have to take care of comparison of each character in the strings so the merge step would be $O(n^2)$. So the recurrence should be of the form

$$T(n) = 2T(\frac n2) + O(n^2)$$

By master's theorem it solves to $O(n^2)$.

Somehow some people on the internet claim the following explanation: Merge sort makes $O(nlogn)$ comparisons and since it is lexicographical sort each comparison take $O(n)$ time, so worst case time is $O(n^2logn)$.

Which of the above is correct and if at some point i am incorrect please correct me.

$\endgroup$
4
$\begingroup$

The recurrence formula is incorrect.

Lets say you have $t$ strings, so the running time of merge isn't $O(t^2)$ but $O(t\cdot n)$.

Change variables: the input size is $m=n^2$, and the recurrence formula should be

$$T(m)=2 T\left( m/2 \right) + O(m) $$

So you get $T(m)=O(m\log(m))$ and therefore $T(n^2)=O(n^2\log(n))$.

$\endgroup$
  • $\begingroup$ I have mentioned that we have n strings of n length, so t = n and txn = nxn = n^2. $\endgroup$ – Navjot Waraich Aug 8 '18 at 12:08
  • 1
    $\begingroup$ Right, but what happens after say $\frac{1}{2}log(n)$ recursive calls? you have $\sqrt n$ strings of size $n$ so the merge step should take $O(\sqrt n \cdot n)$ and not $O(\sqrt n^2)=O(n)$ as your formula suggests. $\endgroup$ – dave Aug 8 '18 at 12:17
  • 2
    $\begingroup$ @JotWaraich The problem is that $n$ changes in the recursive calls, but the string length doesn't. E.g. think about the first recursive step. You have $n/2$ strings to sort, so the merge step will only take $n \cdot n/2$. However in your recursion it would take $(n/2)^2$. So you cannot use the same variable for different things. As dave said, use $t$ in your recursion, or $m$, and afterwards replace $t = n$. $\endgroup$ – Jakube Aug 8 '18 at 12:18
  • 1
    $\begingroup$ @JotWaraich I called the input size $m$ (we usually want to compute the running time of an algorithm as a function of the input size). Often we use $n$ to denote the input size, but in this case n is used to denote the number of strings and the input size is $n^2$. So I've used another letter to denote the input size, i.e. $m=n^2$. $\endgroup$ – dave Aug 8 '18 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.