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


closed as unclear what you're asking by D.W., vonbrand, FrankW, David Richerby, Juho Mar 12 '14 at 9:25

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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.