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