1
$\begingroup$

I need some help understanding how to calculate the lower bound on the time complexity of merging $m$ sorted arrays of length $n$.

The bound should be $nm \lg(m)$. I need to prove this using a decision tree.

I tried counting the number of possible permutations (which would be the number of leaves in the tree) but I got stuck. I tried the following:

When merging the 2nd array with the first, we have $\binom{2n}{n}$ possibilities to place the elements. When merging the 3rd, we have $\binom{3n}{n}$ and so on, so the total number of permutations is:

$$\binom{2n}{n} \binom{3n}{n} \dots \binom{mn}{n}$$

The height of the tree is denoted $h$.

$$h > \lg{\binom{2n}{n} \binom{3n}{n} \dots \binom{mn}{n}}$$

And from here I don't know how to prove the complexity.

My question is - did I count the permutations correctly? Is there a more simple bound? How to continue from here?

Also, ould this problem possibly be equivalent to the problem of sorting an $m$-sorted array of size $nm$? Because in this problem it is easy to prove that the bound is $nm \lg(m)$.

$\endgroup$
  • $\begingroup$ The bound for unsorted arrays is $nm \lg (nm)$, not $nm \lg (m)$. Otherwise let $m = 1$ and voila we have linear time sorting. $\endgroup$ – orlp Aug 10 at 10:58
  • $\begingroup$ You're right, I meant k-sorted with $k=m$. Edited. $\endgroup$ – PhysicsPrincess Aug 10 at 11:06
1
$\begingroup$

Stirling's formula shows that $$ \binom{N}{pN} \sim \frac{2^{H(p)N}}{\sqrt{2\pi p(1-p)N}}, $$ where $H(p)$ is the binary entropy function: $$ H(p) = p\log \frac{1}{p} + (1-p) \log \frac{1}{1-p}. $$ In particular, this shows that for $k \geq 2$, $$ \binom{kn}{n} = (1+o(1)) \frac{2^{H(1/k)kn}}{\sqrt{2\pi(1/k)(1-1/k)kn}} \geq (1+o(1)) \frac{2^{n\log k}}{\sqrt{2\pi n}}. $$ Therefore $$ \log \binom{kn}{n} \geq n\log k - O(\log n), $$ where the big O doesn't depend on $k$. Summing this for $k=2,\ldots,m$, we deduce $$ h \geq n \log m! - O(m\log n) \geq nm \log m - O(nm), $$ using Stirling's formula again.

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