title: n-bit counter amortized analysis
body: <p>Suppose we have a binary counter that supports two operations: incrementing and resetting all bits to zero. If the modification or examination of a single bit takes Theta(1) time, how can a counter be implemented as an array of bits so that any sequence of increment and reset operations on an initially zero counter takes O(n) time? </p>
  
  <p>By aggregate analysis, and considering the fact that not all bits have to flip every time, I was able to see that a counter that just allows incrementing takes O(n) time for n operations. But I'm stuck on how to implement the increment-reset counter. As far as I can tell, a flip is a flip, and nothing will magically make 1111 become 0000 any faster than usual. I do notice, however, that with an increment operation, we won't get a super-expensive all-1s situation too often. </p>
  
  <p>I guess the real question is, is there actually a <em>strategy</em> to realize an efficient counter with the reset utility, or am I merely trying to <em>prove</em> that it would turn out like a counter with just the increment operation? The only hint I have is to "keep a pointer to the high-order 1", which seems to suggest the former. </p>