If you want to make money online : Register now

# prove sufficient number of comparisons for the merge problem

, ,
Problem Detail:

It is given two subsequences. Their length are following: \$2\$ and \$5\$.
I can show that lower bound of comparisons is \$5\$. My problem is that I can't show that \$5\$ is sufficient number of comparisons to merge these subsequences.
In order to show lower bound I use tree of comparisons (number of leaves is \$21\$, so height is at least \$5\$).
However, when it comes to proof of sufficient number of comparison I have no idea. The only idea that comes to my mind is following:
Let our subsequences will be: \$(a, b)\$ and \$(c, d, e, f, g)\$. Let say, that we must use \$k\$ comparisons to find place for \$a\$, where \$k\le 5\$. Now, because of fact that \$b\ge a\$ we must do at most \$5-k\$ additional comparisons. Thus, \$5-k+k=5\$.

You asked about what approach to take, so I'll explain the general approach to take for this kind of problem.

The way to prove that 5 comparisons are sufficient is to exhibit a specific algorithm for merging these two sequences, and prove that your algorithm uses no more than 5 comparisons (no matter what the input is).

So, here's the approach I'd suggest for you, as your next step. Flesh out the algorithm that you have in mind. You seem to have an idea in mind, but take it the rest of the way: actually write down some pseudocode. Then, once you've written it down, try to analyze/upper-bound the number of comparisons your algorithm uses. See if you can prove that it uses at most 5 comparisons. (Try it on some example inputs if you need, to spot a pattern.) If you have proven that it correctly merges the two subsequences and you have proven it will never use more than 5 comparisons, you've proven that 5 comparisons are enough.

On the other hand, if you can't prove that (maybe your algorithm might take more than 5 comparisons on some inputs), you can't conclude anything -- you'll need to keep trying to find another algorithm.