Show that if a DECREMENT operation were included in the \(k\)-bit counter example, \(n\) operations could cost as much as \(\Theta(nk)\) time.

The most costly scenario for DECREMENT is when the counter shows a one followed by \(k-1\) zeros which involves changing all \(k\) bits to produce a zero followed by \(k-1\) ones. Running INCREMENT on that scenario results in the reverse action: changing all \(k\) bits back to a one followed by \(k-1\) zeros. Thus if we alternate between DECREMENT and INCREMENT \(n\) times, we have a worst-case running time of \(\Theta(nk)\).