# Amortized analysis - increment in ternary counter [closed]

What is the amortized analysis of increment action in a ternary counter that is initialized to 0?

• What did you try? Where did you get stuck? Did you try to modify the argument for a binary counter -- it doesn't feel like it should be very different. – David Richerby Jul 17 '19 at 16:22

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
14 - 112
15 - 120
...


We can notice that the bits in the 0th place are changing in every increment operation ($$3^0$$). The bits in the 1th are changing in every 3th increment operation ($$3^1$$). The bits in the 2th place are changing in every 9th increment operation ($$3^2$$). And so on.

The total number of changes equals to the sum of times that every bit has changed. Let's assume $$n\lt 3^{k+1}$$ for some $$k$$. So the total number of changes in $$n$$ increments is no more than $$n+\frac n3+\frac n9+\frac n{3^3}+....+\frac n{3^k} < \frac32n$$ 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).$$