[Solved]: Amortize time for a counter with the operations INCREMENT and DECREMENT

Problem Detail: 

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?

Asked By : AlonAlon

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33350