Consider a k – bit binary counter with increment and decrement operations.

• The INCREMENT operation takes time to increment the counter. That is, if the array A contains all 1s, the INCREMENT operation needs to flip all the k bits.

• The DECREMENT operation also takes time in the worst-case time. That is, when the array A contains all zeros except the most significant bit or A [k-1], DECREMENT operation flips all the k bits.

• Now consider n sequence of INCREMENT and DECREMENT operations on an initially zero counter. Since each INCREMENT or DECREMENT operation takes is time in the worst – case, the worst case cost for a sequence of n INCREMENT and DECREMENT operations is.

Therefore, the cost to run n sequence of INCREMENT and DECREMENT operations on a k -bit binary counter is .