3.6.2 Result 2: Insertion

• Insertion of an element requires at most ${\frac{1}{1 - \alpha}}$ probes on average.
• Proof is obvious because inserting a key requires an unsuccessful search followed by a placement of the key in the first empty slot found.