# Amortize time for a counter with the operations INCREMENT and DECREMENT

Let a binary counter with the operations INCREMENT and DECREMENT.

I need to show that you can't implement this kind of counter with constant amortized time per operation.

Hence, I need to show that there's a series of $N$ operations with amortized time of $\omega(N)$.

My Try:
Let's assume we made $2^k-1$ INCREMENT operations. Hence, our counter is a sequence with $k$ 1's. Now, Let's consider a sequence of $N$ operations alternating between DECREMENT and INCREMENT (DEC,INC,DEC,INC,DEC...)

Each operation must be $\Theta(k)$. Somehow, I need to figure out that it has to be that the amortize time is $\omega(N)$. How?

• A similar question was closed as "unclear what you're asking" earlier in the year, because the asker of that question gave no indication of what they'd tried. However, the present question does include a concrete example of a problem the asker came across while trying to solve the question on their own so I'm pre-emptively commenting that we shouldn't close this as a duplicate. Nov 20, 2014 at 16:14
• Hint: understand the amortised analysis for the standard binary counter example (which only increases). Which are the expensive steps? Try to repeat those as often as possible. Nov 20, 2014 at 18:57

Your solution is on track. As you comment, if you increment a counter $2^k-1$ times and then do $m$ increment/decrement operations, in total you must have modified at least $km$ array positions (this will serve as our lower bound on the running time). In your case $N = 2^k-1 + m$. If you choose, for example, $m = 2^k+1$, then $N = 2^{k+1}$ while the lower bound is $km \geq \log_2 N \cdot (N/2) = \Omega(N\log N)$. This shows that the amortized running time is $\Omega(\log N)$, which is certainly superconstant.
We can easily get a matching (non-amortized) upper bound. If we only perform $N$ operations, then the value of the counter is in the range $[-N,N]$, and so takes $O(\log N)$ bits to represent. It is not difficult to implement increment and decrement so that they take time linear in the length of the representation, so $O(\log N)$ in this case.