Aggregate analysis for a sequence of n operations

Question

I am trying to find the amortized cost for an operation in a sequence of operations n in a data structure in which the operation ith 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 costs to number n , but I'm stuck. I see that the special, more expensive values ​​of i occur by the father and further from each other:

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 don’t have numbers between the first and second degrees 2, then one number, then 3, then 7. When I looked at this for a while, I (correct, if it’s disabled) found that the number of non-strong 2 between degrees jth and jth 2 is 2^(j-1) - 1 .

But how can I link all this together into a summation? I can see something compared to js in combination with the amount of actual permissions of 2, but I had problems with combining all this into a single concept.

Answer 1

I cannot offer a closed form for the sum, but it is clear that the average cost peaks at powers of two with successive such peak values ​​asymptotic up to 3.0 decay to the next power from two to the lower limit, which increases asymptotically to 2.0.

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

You can see both effects in the 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

Amortized cost per step ranges from slightly below 3 (when n is 2) to slightly less than 2 (when n is 1 less than 2), as follows.

We denote K (n) the total cost of n steps, and T (n) denote the cost of degrees 2 that do not exceed n. Let n = 2 ^ j. Then
K(n) = n + T(n) - j
as can be seen from the explanation of the cost of one for each step, then adding the total cost of power in 2 steps and subtracting j for double counting at these 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 amortized cost a little less than 3 when n is a power of 2.

Now suppose that n = 2 ^ (j + 1) -1. We have K(n) = K(2^j) + n - 2^j
(due to n - 2 ^ j step steps after step 2 ^ j), i.e. 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 amortized cost a little less than 2 when n is less than 2.

Answer 3

The amortized cost of one operation will be no more than 3. You can get this either by calculating the total cost of n operations, or dividing it by n, or by the tariffing argument. The charging argument can be constructed as follows.

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

Answer 4

Total cost of n operations -

How did I come to this -

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

Other room rates - Other rooms will have a unit cost.

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