Data Structures and Algorithms
with Object-Oriented Design Patterns in Java 
Computing a tight bound on the worst-case running time of
Program 
is tricky.
Assuming the item to be removed is actually in the table,
then the time required to find the item (lines 10-12) is
in the worst case.
The worst-case running time of the main loop occurs when the table is full, there is only one chain, and no items can be safely moved up in the chain. In this case, the running time of the main loop (lines 15-32) is
Finally, the worst case running time of the last loop (lines 35-42) is O(M).
Therefore, the worst-case running time of the withdraw method for chained scatter tables is
Clearly we don't want to be removing items from a chained scatter table very often!
Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.