need to find the amortized cost of a sequence using the potential function method

Question

There is a sequence of n operations, The ith operation costs 2i if i is an exact power of 2, costs 3i if i is an exact power of 3, and 1 for all other operations.

Hi first up I want to say that it is a homework problem and I don't want you to solve it for me.

I have solved it using the aggregate method. For which I summed up the series of powers of 2 and series of powers of 3 and got amortized cost of 10. I then checked it using the accounting method, for really long sequences and it did not fail. But my problem is how to prove that it would never fail, I can show for as long sequence I want but it would still not guarantee that it would not fail some time after.

Also I tried solving it with the potential function method, this is where I am really stuck, to device a potential function I think you need to be really creative, I cant find some condition which states that at this point this would always hold, need some help there too.

Just some ideas about how to prove it in the accounting method and how to device a potential function should be enough. Thanks

Answer 1

First, forget about the "1 for all other operations" and "exact power of 3" bits for a minute. What if the cost was just 2i when i is an exact power of 2?

Well, suppose we pretend each operation costs four. That is, for each operation, we put four coins into our "IOU pile"... Then we use those coins to "pay" when we hit actual powers of 2. (This is one way of describing the potential function method.)

Step 1: Deposit four coins. Need to pay 2*1 = 2, so our coin pile is at two.

Step 2: Deposit four more coins. Need to pay 2*2 = 4, so our pile is again at two.

Step 3: Deposit four coins. Pile now has six coins.

Step 4: Deposit four coins. Pile now has ten coins, but 4 is a power of 2, so it's time to pay 4*2 = 8, so our pile goes down to two coins again.

Steps 5-7: Deposit four coins each. Total is now 14 coins.

Step 8: Deposit four coins (total = 18), spend 8*2 = 16, once again two coins are left.

It is pretty easy to prove that the steady state here is that we keep depleting our coins down to a constant (2), but we never go below. Therefore the amortized cost is four units per operation.

Now, suppose operation X costs 2i when i is a power of 2 (and zero otherwise). Suppose operation Y costs 3i when i is a power of 3 (and zero otherwise). And suppose operation Z costs 1 except when i is a power of 2 or a power of 3. Observe that your problem is equivalent to performing operation X and Y and Z for every iteration... So if you can figure out the amortized cost of X, Y, and Z separately, you can just sum those to get the overall amortized cost.

I just gave you X; I leave Y and Z as an exercise. (Although I do not believe the final answer is 10. Close to 10, perhaps...)