Amortized analysis on power 3 counter

Question

I was reading the algorithms textbook Cormen, Liserson, Rivest and Stein more often than not.

One of the interesting chapter in there is Amortized analysis. Binary counter is a difficult example when it comes to selecting Potential functions. I was wondering what if the counter if a power of 3 with some co-efficients (ex. x1*1 + x2*3 + x3*9 +...).

How does one decide Potential function in this type of case ?

Answer 1

To prove that incrementing a base-3 counter takes constant amortized time, you can use the potential method with the number of 2s in the current value as the potential function.

An increment operation can be divided into 2 parts:

1. The contiguous 2s at the end of the value are changed to 0.

2. The first digit to the left of those 2s is incremented.

Step (1) takes work proportional to the number of 2s removed from the state.

Each of those 2s is added by Step(2) from a previous operation, which takes constant time and adds at most one 2.

Let Φ be the number of 2s in the current state.

• Step (1) takes takes time proportional to the amount by which it decreases Φ. Since Φ is always >= 0, the total work done in step(1) over many increments is at most proportional to the total amount that Φ has been increased.
• In each increment, Step (2) takes constant time and increases Φ -- the total work that can end up being performed by step (1) --- by at most 1, representing a constant amount of work actually performed, and a constant amount of work queued up for step (1). Together that is a constant amount of work amortized over the current and future increments.