clarification about amortized analysis

Question

I was going through an article here

In the section named Aggregate Method ,the author says

Then summing over the entire sequence, all the 1's sum to O(n), and all the di also sum to O(n). That is,

and then gives this

Σ1≤i≤n ci   ≤   n + Σ0≤j≤m 2j−1

I can understand how summing 1's to get n , But I am not very clear how the second term becomes Σ0≤j≤m 2j−1 and thereby O(n)

Sorry about the formatting..I am not sure how the math notations are to be printed here.. Will you please see the original article ?

Answer 1

I can understand how summing 1's to get n , But I am not very clear how the second term becomes Σ0≤j≤m 2j−1 and thereby O(n)

That is how the algorithm performances (the big-oh) are estimated. It just shows how the algorithm behaves for large number of iterations.

If you do lots of iterations of an algorithm, which has O(1), then they are summed, and that is what your article tells.

Maybe you can look at the your sum as (f(n)-algorithm big-o value)

bigo=0;
for ( int i = 0; i < n; ++ i )
   bigo+=f(n);

which translates for O(1) into : bigo=0; for ( int i = 0; i < n; ++ i ) bigo+=1;

If your f(n) would be O(n), then you would do n*n the iteration loop, and then it would be f(n) :

bigo=0;
for ( int i = 0; i < n; ++ i )
  for ( int j = 0; j < n; ++ j )
     bigo+=1;

HTH