1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – David Richerby Jul 17 at 16:22
2
$\begingroup$

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).$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.