Complexity of Probing :: |
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 |
|