This is a question I have stumbled upon in my textbook, and didn't really know how to approach:

Given a $k$-bit binary counter. We have an operation Increment, which adds 1 to the counter. We add a new operation Decrement, which subtracts 1 from the counter. Prove that the cost for executing $n$ operations is $\Theta(nk)$.

  • $\begingroup$ The $\Theta$-class does not hold. You can show (with amortized analysis), that the cost is ${\cal O}(n)$ (independent of $k$). (Since $\Omega(n)$ is a trivial lower bound, we get $\Theta(n)$. Furthermore it is easy to prove without amortized analysis, that ${\cal O}(n\cdot k)$ is an upper bound.) $\endgroup$ – FrankW Mar 10 '14 at 11:33
  • $\begingroup$ To clarify FrankW's comment, in your case the best that you can expect is for there to be some sequence of operations with amortized cost $\Theta(k)$. In contrast, if there are no decrements, then we have an amortized upper bound of $O(1)$ (which is the same as $\Theta(1)$), whatever the sequence of operations is. $\endgroup$ – Yuval Filmus Mar 10 '14 at 12:13
  • $\begingroup$ This is a dump of an exercise problem, not a question. If you have a specific question regarding the wording of the problem or concrete steps in your own attempts at solving the problem, feel free to edit accordingly and we can reopen the question. See also here for our homework policy, and here for a relevant discussion. You may also want to check out our reference questions. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – D.W. Mar 11 '14 at 0:22
  • $\begingroup$ Hint: to make this kind of question better, include in the question what you've tried, what part you understand, what part you are having trouble with, and try to frame a specific question about your solution -- don't just paste the exercise and expect us to solve it for you. $\endgroup$ – D.W. Mar 11 '14 at 0:22

Hint: Think of a value $n$ such that the transition from $n$ to $n+1$ and back is very costly.


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