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

| cite | improve this answer | |
$\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$

| cite | improve this answer | |
$\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.