Potential Function

We've been analyzing individual while loops with potential functions. This time, we'll analyze the entire ``increment'' operation.

Let x be the current value of the counter. Let $\Phi(x)$ be a potential function that returns the number of ``on'' bits in x.

Let's say each bit flip costs one unit.

The worst-case cost of increment number t is $c_t \le n$. We'll define the amortized cost to be $\hat{c}_t = 2$. That is, we'll pretend that each increment costs 2, even when it's really n (or even if it's 1).