Correctness of lower bound proof

Question

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.

Answer 1

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).