# prove sufficient number of comparisons for the merge problem

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$.
What about this proof ? Maybe you have other approach?

• Your proof doesn't make any sense. Perhaps you should consult a textbook on mathematical reasoning, as the same issue repeats in your other questions. – Yuval Filmus Aug 19 '15 at 22:47

## 1 Answer

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.

• Ok, I understand your approach. However, I ask you for checking my approach. – M.Swe Aug 19 '15 at 18:18
• @M.Swe, I'm afraid that "here's my answer, please check whether my answer is correct" questions are generally considered off-topic for this site, as they aren't a good fit for the Stack Exchange format. See e.g., meta.cs.stackexchange.com/q/597/755 and meta.cs.stackexchange.com/q/519/755. However, asking about what approach to use can often be more suitable. – D.W. Aug 19 '15 at 18:27
• Ok, I try to understand you. Nevertheless, otherwise You tell me: it is your homework, you should show us your attemptions. And it is why I show my attemption. – M.Swe Aug 19 '15 at 18:38
• @M.Swe, I hear you. You're not the only one who has found this confusing. We ask you to make an attempt to solve the problem and show what you've tried, to help you ask a more specific, narrowly focused question about your attempt. We don't want "Here's my exercise, please solve it for me", and we don't want "Here's my exercise, here's my answer, please tell me whether your answer is correct". However, "Here's my exercise, here's what I tried, however I got stuck at the following step, which made me realize I don't understand how to do task X -- how do I do that?" can sometimes be suitable. – D.W. Aug 19 '15 at 18:47
• Ok, sometimes someone has a problem with solve task, my problem is different (but it is also problem). Is my solution is properly ? So what should I do in order to you help me ? – M.Swe Aug 19 '15 at 18:51