Binary Counter Amortized Analysis

Question

I guess you already know that if all the entries in the Array starts at 0 and at each step we increment the counter by 1 (by flipping 0's and 1's) then the amortized cost for k increments is O(k).

But, what happens if the Array starts with n ? I though that maybe the complexity for k increments is now O(log(n) + k), because of the fact that in the beginning the maximum number of 1's is log(n).

Any suggestions ?

Thanks in advance

Answer 1

You are right. There is more than one way to prove this, one of them is with a potential function. This link (and many others) explain the potential method. However, textbooks usually require that the initial value of the potential function is 0. Let's generalise for the case that it is not.

For the binary counter, the potential function of the counter is the number of bits set to 1. When you increment, you spend k+1 time to flip k 1's to 0 and one 0 to 1. The potential decreases by k-1. So the amortised time of this increment = ActualTime+(PotentialAfter-PotentialBefore) = k+1-(k-1) = 2 (constant).

Now look at the section "Relation between amortized and actual time" in the wikipedia link.

TotalAmortizedTime = TotalActualTime + SumOfChangesToPotential

Since the SumOfChangesToPotential is telescoping, it is equal to FinalPotential-InitialPotential. So:

TotalAmortizedTime = TotalActualTime + FinalPotential-InitialPotential

Which gives:

TotalActualTime = TotalAmortizedTime - FinalPotential + InitialPotential <= TotalAmortizedTime + InitialPotential

So, as you say, the total time for a sequence of k increments starting with n is O(log n + k).