Complexity of Probing ::

Lower bound of 3n-3

This section proves a lower bound of 3n-3 probes on the complexity of shape discovery algorithms. This section first describes a terminology and data structures used in the proof. It then describes a set of inductive properties necessary for the proof. This is followed by a description of an adversary algorithm. Finally, the section culminates in a proof of the lower bound.

Complexity of Probing

Data Structures