# Find a recurrence relation for merging of sublists of an array

There are $\log n$ sublists each of size $\frac{n}{\log n}$. Write a recurrence relation for merging these lists into an $n$ element list.

My Approach Let $m = \log n$. Then, $T(m) = 2T(m/2) + O(n)$, where $O(n)$ is for merge algorithm.

We get $T(m) = 2T(m/2) + O(2^{m})$.

Now solving we get $T(m) = O(n)$.

But intuitively there are $O(\log\log n)$ levels each doing $O(n)$ work so complexity to merge should be $O(n\log\log n)$. Where am I wrong? Please help. Tried hard but unable to get loophole.

## 2 Answers

The mistake is when converting $O(n)$ to $O(2^m)$, and then varying $m$. In fact, $n$ is constant here and $m$ changes. So the recurrence relation is $T(m) = T(m/2) + O(n)$, whose solution is $T(m) = O(n\log m)$. Substituting $m = \log n$, we obtain $O(n\log\log n)$.

The same recurrence relation for the merge sort will work by changing just base conditions.

$$T(n) = T(n/2) + \theta(n); \ n> \frac{n}{log_2n}$$

and, $$T(\frac{n}{log_2n})= \theta(1)$$

By solving above equation we get,

$$T(n)=log_2n+nlog_2log_2n$$