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
    ...

Answer 2

The amortized cost per step ranges from slightly below 3 (when n is a power of 2) down to slightly less than 2 (when n is 1 less than a power of 2), as follows.

Let K(n) denote the total cost of n steps, and let T(n) denote the cost of powers of 2 that do not exceed n. Suppose n = 2^j. Then
K(n) = n + T(n) - j
as seen by attributing a cost of one to every step, then adding the total cost of power-of-2 steps, and subtracting j for double-counts on those steps. Because
T(2^j) = 1 + 2 + 4 +...+ 2^j = 2^(j+1)-1 = 2*n-1,
we have
K(n) = 3*n - j - 1,
for an amortized cost of slightly less than 3 when n is a power of 2.

Now suppose n = 2^(j+1)-1. We have
K(n) = K(2^j) + n - 2^j
(because of n - 2^j unit-cost steps after step 2^j ), ie
K(n) = (3*2^j - j - 1) + (2^(j+1) - 1) - 2^j,
or
K(n) = 2*(2^(j+1)-1) - j = 2*n - j,
for an amortized cost of slightly less than 2 when n is one less than a power of 2.

Answer 3

The amortized cost per operation would be at most 3. You can obtain this either by computing the total cost of the n operations and dividing it by n, or by a charging argument. The charging argument can be constructed as follows.

When i is not a power of 2, charge cost 1 to i. Otherwise when i is of the form 2^k, the operation cost would be 2^k, which wan be redistributed between the operations in the positions: [2^{k-1}+1, 2^k]. This can be done by increasing the charge of each operations in [2^{k-1}+1, 2^k-1] positions by 2 and assigning the remaining charge 2 to the operation at 2^k position. After the redistribution, the maximum charge at any position is 3.

Answer 4

The total cost of n operations -

How I arrived at this -

The cost of the powers of 2 - The sum of the first n powers of 2 is . Since I needed the powers of the numbers up to n, I replaced n with the floor of log n.

Cost of the other numbers - There will be numbers remaining having unit cost.

Add both of them up and you will arrive at the equation.