Question

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

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top