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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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))$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I have mentioned that we have n strings of n length, so t = n and txn = nxn = n^2. $\endgroup$
    – Navjot Singh
    Aug 8, 2018 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, 2018 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, 2018 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, 2018 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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