0

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 ?

0

1 Answer 1

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.