Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Worst-Case Running Time

Computing a tight bound on the worst-case running time of Program gif is tricky. Assuming the item to be removed is actually in the table, then the time required to find the item (lines 9-11) is

displaymath62101

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 14-31) is

displaymath62102

Finally, the worst case running time of the last loop (lines 33-40) is O(M).

Therefore, the worst-case running time of the Withdraw method for chained scatter tables is

displaymath62103

Clearly we don't want to be removing items from a chained scatter table very often!


next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.