2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Unfortunately, your argument doesn't constitute a proof. It's just a bunch of intuitions. $\endgroup$ – Yuval Filmus May 19 '18 at 18:29
  • $\begingroup$ The problem statement isn't completely clear. What is the output of the algorithm? $\endgroup$ – Yuval Filmus May 19 '18 at 18:38
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus May 19 '18 at 18:39
  • $\begingroup$ 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? $\endgroup$ – John May 19 '18 at 18:52
  • $\begingroup$ 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. $\endgroup$ – John May 19 '18 at 19:20
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – John May 19 '18 at 19:34
  • $\begingroup$ Unfortunately there are some subtleties which need to be addressed. Note that I am using the decision tree model. $\endgroup$ – Yuval Filmus May 19 '18 at 20:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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