1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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)$.

$\endgroup$
0
$\begingroup$

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$

$\endgroup$

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.