title: amortized cost of modified increment function
body: <p>So the scenario goes, the increment algorithm, for n bit binary string A[0....n-1], where A[0] is the least significant bit and A[n-1] is the most significant bit, is:</p>
  
  <pre><code>Increment(A,n):
  i←0
  while i&lt;k and A[i]=1 do
     A[i] ← 0
     i ← i+1
  if i &lt; k then
     A[i] ← 1
  </code></pre>
  
  <p>But the cost to flip a bit at index k is 2^k</p>
  
  <p>I'm lost on trying to prove that the amortized cost of this modified binary increment algorithm is O(logn). No matter how I try to approach, it still seems like the amortized cost would be big O(1), though with a bigger constant. </p>
  
  <p><a href="https://i.stack.imgur.com/BLXiX.jpg" rel="nofollow noreferrer">aggregated analysis of the increment function.</a>
  if I follow up on this breakdown and multiply by 2^i inside the sigma, since for the cost of flipping the ith bit is 2^i, I get nk for n increments. Which still gives me amortized cost of O(1)</p>
  
  <p>I am not sure what I'm doing wrong here. Intuitively it makes sense for it to be still O(1) since the high cost higher bits just cancels out the low probability of it being flipped. </p>