Consider a base-3 counter : each digit can be one of 0, 1, 2. The cost of increment operation is number of digits that get changed. What is the amortized cost of this operation? Design an appropriate potential function.
I could do it in aggregate method: The amortized cost per increment will be O(1). In order to show it let's use the aggregate method.
0 - 000 1 - 001 2 - 002 3 - 010 4 - 011 5 - 012 6 - 020 7 - 021 8 - 022 9 - 100 10 - 101 11 - 102 12 - 110 13 - 111 ... We can notice that the bits in the 0th place are changing in every increment operation (30). The bits in the 1th are changing in every 3th increment operation (31). The bits in the 2th place are changing in every 9th increment operation (32). And so on.
The total number of changes equals to the sum of times that every bit has changed. Let's assume n<3k+1 for some k. So the total number of changes in n increments is no more than n+n3+n9+n33+....+n3k<32n Assuming it takes O(1) to perform the change of one bit and the associated bookkeeping, the total cost of the sequence is O(n). So the amortized cost per operation is O(n)/n=O(1).