# Correctness of lower bound proof

I am working on this exercise with the purpose of learning how to provide proper proofs and I would like to know if my proof for the following problem is correct.

Given a sorted array $A$ (of $n$ distinct elements) and three elements $x$, $y$, and $z$, where $x < y < z$. The problem is to determine whether $x$, $y$, and $z$ are in $A$ or not. Prove that any comparison-based algorithm for this problem needs at least $3\log n-c$ comparisons in the worst case, where $c > 0$ is some constant.

My current proof using a decision tree goes as follows: A comparison based algorithm must have at least 2 outcomes per a single comparison. For example: >= or <. It can also have 3 outcomes: < or = or >. But it has to have at least two.

When trying to decide whether an element is in the array or not it could be equal to any of the $n$ elements or it might not be in the array. Thus we have $n+1$ leaves in the decision tree.

Because of this the height of the decision tree is at least $\log_2(n+1)$. This is a lower bound for deciding whether one element is in the array or not. If we want to decide if the 3 elements $x, y, z$ are in the array or not and we know that $x< y< z$ we can use this information to speed up the search by searching for $y$ first.

For example if the outcome of the first comparison is < then since we know that $x < y$ we can skip that comparison when searching for $x$ and save at least a step. Similarly, if the outcome of the first comparison is > then since we know $y < z$ we don’t have to redo that comparison when searching for $z$ and save at least one step.

So if the search for $y$ starts with some constant $c$ left-branches we save that many steps when searching for $x$ and if the search for $y$ starts with $c$ right-branches we save that many steps when searching for $z$.

Thus, if it takes $k$ steps in the worst case to search for the 3 elements a lower bound is: $$k \ge 3\log_2(n+1)-c \ge 3\log_2 n-c,$$ where $c$ is some positive constant.

Is this a correct proof? What I am unsure about is if the last statement is ok, where I just discard the "+1". And whether this holds true for "any comparison based algorithm". Any critique or suggestions are greatly appreciated.

• Unfortunately, your argument doesn't constitute a proof. It's just a bunch of intuitions. May 19, 2018 at 18:29
• The problem statement isn't completely clear. What is the output of the algorithm? May 19, 2018 at 18:38
• Very roughly speaking, you should get $3\log_2 n - O(1)$ since there are roughly $\binom{n}{3}$ possible positions for $x,y,z$, and $\log_2 \binom{n}{3} = 3 \log_2 n - O(1)$. However there are many missing details. May 19, 2018 at 18:39
• Could you please elaborate on how (n chose 3) positions becomes 3log2(n)-O(1) and how x<y<z has any to do with this?
– John
May 19, 2018 at 18:52
• Just to clarify. The problem is given in full and no extra information should be needed. It should also be possible to solve it using a decision tree. The index/null is just an interpretation I did. It might be wrong/unnessesary and should not be considered a part of the problem. I am sorry for any misunderstanding. However the end result is simply to decide if x,y,z are in A or not. Thats it.
– John
May 19, 2018 at 19:20

The following answer works for a previous variant of the question, in which the goal is to determine which of $x,y,z$ are in $A$. It might be possible to adapt it to the current version, in which the goal is to determine whether or not all of $x,y,z$ are in $A$. One difficulty is that the number of trees of depth $h$ is now $\Theta(2^hh^3)$, so following the same steps would only give a lower bound of $3\log_2 n - \Theta(\log \log n)$.

Suppose that the array $A$ is $1,\ldots,n$. Let $x = i + 1/2$, $y = j + 1/2$, $z = k + 1/2$, where $1 \leq i < j < k < n$ are integers. Let us denote the resulting leaf of the algorithm by $\ell(i,j,k)$.

I claim that if $(i,j,k) \neq (i',j',k')$ then $\ell(i,j,k) \neq \ell(i',j',k')$. Indeed, suppose that $\ell(i,j,k) = \ell(i',j',k')$ although $(i,j,k) \neq (i',j',k')$. Suppose that $i < i'$ (the other cases are similar). Since $i + 1/2 < A_{i+1} < i' + 1/2$, we conclude that in this computation path, the algorithm never compares $x$ to $A_{i+1}$. Suppose that we change $A_{i+1}$ to $A'_{i+1} = i + 1/2$. The new array $A'$ is still sorted, and when running the algorithm on $A',i+1/2,j+1/2,k+1/2$, it still reaches the leaf $\ell(i,j,k)$ (since the only comparison whose answer is different is $A'_{i+1}$ and $x$). We have reached a contradiction, since $x \in A'$, and so we should have reached a different leaf.

Concluding, we have shown that the algorithm tree must have at least $\binom{n-1}{3}$ different leaves (this is the number of possible triples $(i,j,k)$). Since we are only considering runs of the algorithm in which the answers to all comparison queries are either $<$ or $>$, we can ignore all edges labeled $=$, and so we are left with a binary tree, whose depth must therefore be at least $\log_2 \binom{n-1}{3}$. This is a lower bound on the number of comparisons in the worst case.

When $n \geq 4$, we have $$\binom{n-1}{3} = \frac{(n-1)(n-2)(n-3)}{6} \geq \frac{(n-3)^6}{6} \geq \frac{(n/4)^3}{6} = \frac{n^3}{384},$$ since $n-3 \geq n/4$. Therefore for $n \geq 4$ the number of comparisons must be at least $$\log_2 \frac{n^3}{384} = 3\log_2 n - \log_2 384.$$ When $1 \leq n \leq 3$, we must still make (say) at least one comparison, and this allows us to obtain a lower bound of $3\log_2 n - c$ valid for all $n \geq 1$ (details left to the reader).

• Thank you for your answer. But this seems way beyond our scope. Especially the contradiciton part. This is supposed to be a somewhat simple exercise that is to be solved using a decision tree. The purpose is just to teach us to give lower bound proofs. The algorithm should just answer the question wheather x,y,z are in A or not. Also there is no limit on n>=4. Is there a way to make it more simple using a decision tree?
– John
May 19, 2018 at 19:34
• Unfortunately there are some subtleties which need to be addressed. Note that I am using the decision tree model. May 19, 2018 at 20:05