Design and Analysis of Algorithms

Examples of Complexity Calculation 413

15.3.7 Sets vs. Bags and Mappings

So far we have emphasized structures for storing sets. However, most of these structures can also be adapted

to implement bags and mappings as well. Usually it is a matter of storing additional information with the

element inside the representation. For example, with bags we store a number indicating the multiplicity of the

element in the bag; the absence of an element implies multiplicity 0.

With mappings, the elements stored in the set are the domain values, and with each element in the

domain we store the corresponding range value.

15.4 AMORTIZED ANALYSIS

The word “amortized” is borrowed from the practice of accountancy, and means spreading the cost of some

expensive ...