0
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\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
    Commented Mar 10, 2014 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
    Commented Mar 10, 2014 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. ♦
    Commented Mar 11, 2014 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. ♦
    Commented Mar 11, 2014 at 0:22

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$

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