Lower bound for merging $m$ sorted arrays (decision tree leaves count - permutations)
-
05-11-2019 - |
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