I'm doing the CLRS Problems and there's a part I'm having trouble following.

The question is: Part a) Given 2n numbers, compute the number of possible ways to divide them into two sorted lists, each with n numbers.

Part b) Using a decision tree and your answer to part (a), show that any algorithm that correctly merges two sorted lists must perform 2n−o(n) comparisons.

Part a) makes senses to me. The first line to the solutions of part b) states any decision tree to merge two sorted lists must have at least $2n$ choose $n$ leaf nodes.

I don't follow why this is. In particular, what is each branch comparing to get to this result? And what does each leaf node represent?


1 Answer 1


Let us consider any comparison-based algorithm for merging two ordered lists $A,B$ of length $n$, focusing on the case in which all $2n$ numbers are distinct. When the algorithm terminates, the results of the comparisons determine the merged list. Stated differently, if we describe the algorithm as a decision tree, then each leaf is labelled with the merged list, which is some permutation of the elements in $A \cup B$. Since all elements are different, each possible such permutation must be represented as some leaf.

Since the lists $A = (a_1,\ldots,a_n)$ and $B = (b_1,\ldots,b_n)$ are ordered, the permutation $\pi$ labeling each leaf must satisfy the following property: if $i < j$ then $a_i$ appears before $a_j$ and $b_i$ appears before $b_j$. This implies that $\pi$ is determined from the set of indices containing elements of $A$. There are $\binom{2n}{n}$ such possible sets, and all corresponding permutations can actually happen, as can be seen by assigning the element in the $k$th the number $k$. For example, if $n = 2$ then the possible orders are:

  1. $a_1,a_2,b_1,b_2$ – achieved for $A = 1,2$ and $B = 3,4$.
  2. $a_1,b_1,a_2,b_2$ – achieved for $A = 1,3$ and $B = 2,4$.
  3. $a_1,b_1,b_2,a_2$ – achieved for $A = 1,4$ and $B = 2,3$.
  4. $b_1,a_1,a_2,b_2$ – achieved for $A = 2,3$ and $B = 1,4$.
  5. $b_1,a_1,b_2,a_2$ – achieved for $A = 2,4$ and $B = 1,3$.
  6. $b_1,b_2,a_1,a_2$ – achieved for $A = 3,4$ and $B = 1,2$.

Therefore the decision tree must contain at least $\binom{2n}{n}$ leaves. Since it is binary (we assumed that no two elements are equal), its depth must be at least $\log_2 \binom{2n}{n}$. Stirling's approximation shows that $\binom{2n}{n} = 4^n/\Theta(\sqrt{n})$, hence $\log_2 \binom{2n}{n} = 2n - \Theta(\log n)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.