Question

Suppose we perform a sequence of n operations on a data structure in which the ith operation costs logi if
i is an exact power of 2, and 1 otherwise. Use two different methods to determine the amortized cost per
operation.

Answer 1

Design and Analysis of Algorithms:

1. If the set of stack operations included a MULTIPUSH operation, which pushes k items onto the stack, would the O(1) bound on the amortized cost of stack operations continue to hold? No. The time complexity of such a series of operations depends on the number of pushes (pops vise versa) could be made. Since one MULTIPUSH needs Θ(k) time, performing n MULTIPUSH operations, each with k elements, would take Θ(kn) time, leading to amortized cost of Θ(k).

2. Suppose we perform a sequence of n operations on a data structure in which the ith operation costs i if i is an exact power of 2, and 1 otherwise. Use aggregate analysis to determine the amortized cost per operation. In a sequence of n operations there are blog2 nc+1 exact powers of 2, namely 1,2,4,...,2 blog2 nc . The total cost of these is a geometric sum ∑ blog2 nc i=0 2 i = 2 blog2 nc+1 −1 ≤ 2 log2 n+1 = 2n. The rest of the operations are cheap, each having a cost of 1, and there are less than n such operations. The total cost of all operations is thus T(n) ≤ 2n+n = 3n = O(n), which means O(1) amortized cost per operation.

IV-3 (CLRS 17.2-2 and CLRS 17.3-2) Redo the previous exercise using (a) an accounting method of analysis and (b) a potential method of analysis.

(a) The actual cost of the ith operation is

ci = ( i if i is an exact power of 2

  1 otherwise.)

We assign the amortized costs as follows:

cˆi = ( 2 if i is an exact power of 2

3 otherwise.)

Now an operation, which is an exact power of 2 uses all previously accumulated credit plus one unit of its own amortized cost to pay its true cost. It then assigns the remaining unit as credit. On the other hand, if i is not an exact power of 2, then the operation uses one unit to pay its actual cost and assigns the remaining two units as credit. This covers the actual cost of the operation. We still have to show that there will always be enough credit to pay the cost of any power-of-2 operation. Clearly this is the case for the first operation (i = 1), which happens to be an exact power of two. Let now j > 0. After 2j−1 :th operation there is one unit of credit. Between operations 2j−1 and 2j there are 2j−1 −1 operations none of which is an exact power of 2. Each assigns two units as credit resulting to total of 1+2 ·(2 j−1 −1) = 2 j −1 accumulated credit before 2j th operation. This, together with one unit by its own, is just enough to cover its true cost. Therefore the amount of credit stays nonnegative all the time, and the total amorized cost is an upper bound for the total actual cost.

(b) We define the potential function as follows:

Φ(D0) = 0 and Φ(Di) = 2i−2 blog2 ic+1 +1 for i > 0. (Note that Φ(Di) actually equals to the amount of credit after ith operation in previous exercise.) This potential is always nonnegative, so we have Φ(Di) ≥ 0 = Φ(D0) for all i. Now • For i, which is an exact power of 2, the potential difference is Φ(Di)−Φ(Di−1) = (2i−2i+1)−(2(i−1)−i+1) = 2−i Note that this also holds for i = 1. Thus, the amortized cost of ith operation is cˆi = ci +Φ(Di)−Φ(Di−1) = i+2−i = 2. 1 • For i, which is not an exact power of 2, the potential difference is Φ(Di)−Φ(Di−1) = (2i−i+1)−(2(i−1)−i+1) = 2. Thus, the amortized cost of ith operation is cˆi = ci +Φ(Di)−Φ(Di−1) = 1+2 = 3. As seen above, the amortized cost of each operation is O(1).

4. What is the total cost of executing n of the stack operations PUSH, POP, and MULTIPOP, assuming that the stack begins with s0 objects and finishes with sn objects? Let Φ be the potential function that returns the number of elements in the stack. We know that for this potential function, we have amortized cost 2 for PUSH operation and amortized cost 0 for POP and MULTIPOP operations. The total amortized cost is

Using the potential function and the known amortized costs, we can rewrite the equation as

  

which gives us the total cost of O(n + (s0 − sn)). If sn ≥ s0, then this equals to O(n), that is, if the stack grows, then the work done is limited by the number of operations. (Note that it does not matter here that the potential may go below the starting potential. The condition Φ(Dn) ≥ Φ(D0) for all n is only required to have , but we do not need for that to hold in this application.)

5.   Suppose that instead of contracting a table by halving its size when its load factor drops below 1/4, we contract it by multiplying its size by 2/3 when its load factor drops below 1/3. Using the potential function Φ(T) = |2 ·N(T) − S(T)|, show that the amortized cost of a TABLE-DELETE that uses this strategy is bounded above by a constant. Here N(T) and S(T) denote the number of items stored in table T and the size of T, respectively.

Let ci denote the actual cost of the ith operation, ˆci its amortized cost and ni , si and Φi the number of items stored in the table, the size of the table and the potential after the ith operation, respectively. The potential Φi cannot get negative values and we have Φ0 = 0. Therefore Φi ≥ Φ0 for all i and the total amortized cost provides an upper bound on the actual cost.

Now if the ith operation is TABLE-DELETE, then ni = ni−1 −1. Consider first the case when the load factor does not drop below 1/3, i.e. ni si−1 ≥ 1 3 . Then the table isn’t contracted and si = si−1. We pay ci = 1 for deleting one item. Thus

   = 1+|2ni −si | −|2ni−1 −si−1|

= 1+|2ni−1 −si−1 −2| −|2ni−1 −si−1| ni = ni−1 −1, si = si−1

≤ 1+|(2ni−1 −si−1 −2)−(2ni−1 −si−1)| (reverse) triangle inequality

= 1+2 = 3

Now consider the case when the load factor drops below 1/3, i.e.

ni/( si−1) < 1/ 3 ≤ ni−1/ si−1

⇒ 2ni < (2/ 3) si−1 ≤ 2ni +2. (1)

Now we contract the table and have

si = [(2/3) ·si−1] ⇒( 2/ 3) si−1 −1 ≤ si ≤ (2/ 3) si−1. (2)

By combining (1) and (2) we get 2ni −1 ≤ si ≤ 2ni +2 and thus |2ni −si | ≤ 2. Furthermore, from (1) we get si−1 > 3ni and thus |2ni−1 −si−1| = −2ni−1 +si−1 ≥ ni−1. We pay ci = ni +1 for deleting one item and moving the remaining ni items into the contracted table. Then,

cˆi = ci +Φi −Φi−1

= (ni +1) +|2ni −si | −|2ni−1 −si−1|

≤ (ni +1) +2−ni = 3

In both cases the amortized cost is at most 3 and thus bounded above by a constant.