Lower bound of 3n-1

Cole and Yap [1] include another interesting proof in their paper. They use a method similar to that shown in the previous section to prove that the lower bound on the complexity of any shape discovery algorithm can be raised to 3n-1 probes. The proof for this last results takes 7 pages out of the 19 pages of this paper. It will not be covered in this tutorial.  

Proof

Applet