Complexity of Probing :: 
This section proves a lower bound of 3n3 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 
