You must find the amortized cost of the sequence using the potential function method.

Question

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

Hi, first I want to say that this is a homework problem, and I do not want you to solve it for me.

I solved this using the aggregated method. Why did I summarize a series of degrees 2 and a series of degrees 3 and got an amortized cost of 10. Then I checked it using the accounting method for really long sequences, and this did not fail. But my problem is how to prove that it will never fail, I can show that as long as I want, but it still does not guarantee that it will not end some time later.

And I tried to solve it using the potential function method, this is where I really got stuck to make the device a potential function. I think you need to be really creative, I can’t find any condition that says that at the moment it will always need help.

Just some ideas on how to prove this in the accounting method and how to use the potential function should be sufficient. Thanks

Answer 1

First, forget about “1 for all other operations” and “exact power 3” bits for a minute. What if the cost was 2i when i am the exact power of 2?

Well, suppose we pretend that each operation costs four. That is, for each operation, we put four coins in our “IOU heap” ... Then we use these coins to “pay” when we press the actual authority 2. (This is one way to describe the potential function method).

Step 1: Deposit four coins. You need to pay 2 * 1 = 2, so our pile of coins is doubled.

Step 2: Deposit four more coins. You need to pay 2 * 2 = 4, so our bunch again for two.

Step 3: Deposit four coins. There are six coins in the heap now.

Step 4: Deposit four coins. The heap now has ten coins, but 4 is the power of 2, so you need to pay 4 * 2 = 8, so that our pile will again drop to two coins.

Steps 5-7: Deposit four coins each. There are 14 coins in total.

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

It is fairly easy to prove that a steady state is that we continue to deplete our coins to a constant (2), but we never sink below. Therefore, the amortized cost is four units per transaction.

Now suppose that operation X costs 2i when i equals 2 (and zero otherwise). Suppose operation Y costs 3i when i am cardinality 3 (and zero otherwise). And suppose operation Z is worth 1, unless I am power 2 or power 3. Note that your problem is equivalent to performing operations X and Y and Z for each iteration ... Therefore, if you can determine the amortized cost X, Y and Z separately, you can simply sum them up to get the total amortized cost.

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