 Rock Street, San Francisco

We do not always know in advance how many objects some applications will storein a table. We might allocate space for a table, only to find out later that it is notenough. We must then reallocate the table with a larger size and copy all objectsstored in the original table over into the new, larger table. Similarly, if many objectshave been deleted from the table, it may be worthwhile to reallocate the table witha smaller size. In this section, we study this problem of dynamically expanding andcontracting a table. Using amortized analysis, we shall show that the amortized costof insertion and deletion is only O.1/, even though the actual cost of an operationis large when it triggers an expansion or a contraction. Moreover, we shall see howto guarantee that the unused space in a dynamic table never exceeds a constantfraction of the total space.We assume that the dynamic table supports the operations TABLE-INSERT andTABLE-DELETE. TABLE-INSERT inserts into the table an item that occupies a single slot, that is, a space for one item. Likewise, TABLE-DELETE removes an itemfrom the table, thereby freeing a slot. The details of the data-structuring methodused to organize the table are unimportant; we might use a stack (Section 10.1),a heap (Chapter 6), or a hash table (Chapter 11). We might also use an array orcollection of arrays to implement object storage, as we did in Section 10.3.We shall find it convenient to use a concept introduced in our analysis of hashing(Chapter 11). We define the load factor ?.T / of a nonempty table T to be thenumber of items stored in the table divided by the size (number of slots) of thetable. We assign an empty table (one with no items) size 0, and we define its loadfactor to be 1. If the load factor of a dynamic table is bounded below by a constant,464 Chapter 17 Amortized Analysisthe unused space in the table is never more than a constant fraction of the totalamount of space.We start by analyzing a dynamic table in which we only insert items. We thenconsider the more general case in which we both insert and delete items. 