Aggregate analysis for a sequence of n operations

Question

I'm trying to find the amortized cost per operation in a sequence of n operations on a data structure in which the ith operation costs i if i is an exact power of 2, and 1 otherwise.

I think I need to find a way to express the sum of the costs up to a number n, but I'm stuck. I can see that the special, more expensive i values are occurring father and farther apart:

i = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20...

So, it looks like I have no numbers between the first and second powers of 2, then one number, then 3, then 7. When I looked at this a while, I (correct me if this is off) found that the number of non-powers of 2 between the jth and kth powers of 2 is 2^(j-1) - 1.

But how can I tie this all together into a summation? I can kind of see something over the js combined with the number of actual powers of 2 themselves, but I'm having trouble uniting it all into a single concept.

Answer 1

I can't offer a closed form for the sum, but it's clear that the average cost peaks at powers of two with successive such peak values asymptotic to 3.0, decaying before the next power of two to a lower limit that rises asymptotically toward 2.0.

Each of the (2^n) - 1 values strictly between 2^n and 2^(n+1) contributes 1 to the total cost (causing the average to decay downward) until the value at 2^(n+1) adds 2^(n+1). Therefore the average contribution of the segment beginning after 2^n and ending with 2^(n+1) is ((2^n)-1 + 2^(n+1)) / 2^n or (3 * 2^n - 1) / 2^n, which approaches 3 as n increases.

You can see both effects in the excerpted table below. Hope this helps.

      i       sum  average
-------   -------  -------
      1:        1  1.00000
      2:        3  1.50000
      3:        4  1.33333
      4:        8  2.00000
    ...
      7:       11  1.57143
      8:       19  2.37500
    ...
     15:       26  1.73333
     16:       42  2.62500
    ...
     31:       57  1.83871
     32:       89  2.78125
    ...
     63:      120  1.90476
     64:      184  2.87500
    ...
    127:      247  1.94488
    128:      375  2.92969
    ...
    255:      502  1.96863
    256:      758  2.96094
    ...
    511:     1013  1.98239
    512:     1525  2.97852
    ...
   1023:     2036  1.99022
   1024:     3060  2.98828
    ...
   2047:     4083  1.99463
   2048:     6131  2.99365
    ...
   4095:     8178  1.99707
   4096:    12274  2.99658
    ...
   8191:    16369  1.99841
   8192:    24561  2.99817
    ...
  16383:    32752  1.99915
  16384:    49136  2.99902
    ...
  32767:    65519  1.99954
  32768:    98287  2.99948
    ...
  65535:   131054  1.99976
  65536:   196590  2.99973
    ...
 131071:   262125  1.99987
 131072:   393197  2.99986
    ...
 262143:   524268  1.99993
 262144:   786412  2.99992
    ...
 524287:  1048555  1.99996
 524288:  1572843  2.99996
    ...
1048575:  2097130  1.99998
1048576:  3145706  2.99998
    ...