snippetMinor
Merge sort worst case running time for lexicographical sorting?
Viewed 0 times
casesortingmergetimelexicographicalrunningforsortworst
Problem
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.
$$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.
Solution
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))$.
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))$.
Context
StackExchange Computer Science Q#96075, answer score: 4
Revisions (0)
No revisions yet.