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 ?

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

• what exactly does the term `2^(j-1)` mean here? how is it derrived? Jun 21, 2013 at 6:36
• @damon The coefficient doesn't matter. O(2*n) is O(n) Jun 21, 2013 at 6:39