You are in the right track.But try to see the code in this way for ease of visualization...

```
for(int i = 0; i < n-1; i++)
{
x=(int)pow(2,i);
for(int j = 1; j <= x; j++)
cout << j << endl;
}
```

You can see that here too x and i vary as x = 2 power i just like in your code.

So as you can see the complexity turns out to be

==> Summation where i ranges from 0 to n-2( Summation where j ranges from 1 to 2 power i( 1 ))

==> Summation where i ranges from 0 to n-2( 2 power i )

==> (2 power 0) + (2 power 1) + (2 power 2) + (2 power 3) + ...... + (2 power (n-2))

And you can see that (2 power 0) + (2 power 1) = (2 power 2) - 1;

(2 power 0) + (2 power 1) + (2 power 2) = (2 power 3) - 1 and so on ... Therefore above problem comes to

==> (2 power (n-1)) - 1

And thats your complexity or Big-Oh.Hope you understand...Cannot put it in any better way :)

==> (2 power (n-1)) - 1

And thats your complexity or Big-Oh.Hope you understand...Cannot put it in any better way :)

Actually, you can -- because O(2^(n-1)-1) is the same as O(2^n).

To see this, realize that when you're talking about big-O notation, adding or subtracting a constant, or multiplying or dividing by a constant, makes no difference. So

O(2^(n-1)-1) is the same as

O(2^(n-1)), which is the same as

O((2^n)/2), which is the same as

O(2^n).

I think I get it now. In my original post I was using 2^n in my summation formula but csurfer corrected my problem by writing it as 2^i. 'n' didn't make sense because it never changes.

So, my new summation formula is:

Summation of 2^i + 1 from i = 0 to n-2. This gives the number of times the inner for loop is executed. Then I broke this up into summation of 2^i and summation of 1 and simplified using the summation formulas for k^i and k(k = constant).

=> 2^(n-1) - 1 + n - 2

=> 2^n * 2^-1 -1 +n -2

Then I ignored the coefficients, lower powers, and constants so O(2^n) is the answer

Thanks for the help!

>>

Summation of 2^i + 1 from i = 0 to n-2.That shows right there that its O(n*2^n);

@first person :

==> Summation where i ranges from lowerlimit to upperlimit( 1 )

==> (upperlimit - lowerlimit + 1)

Therefore its

==> Summation of 2^i where i ranges from 0 to n-2

and not Summation of 2^i+1 where i ranges from 0 to n-2.

Therefore final complexity is 2^(n-1) - 1

which can be stated as BigOh(2^n) and not BigOh(n*2^n) as you said.

Please recheck and correct me if I am wrong.

Just to see what you are thinking, can you explain how you got that in terms of summation, as you did in your proof couple of post ago. I just want to see exactly where we differ and see if I am wrong or if you are wrong.

@firstPerson : Sure here it is..

The code is actually interpreted as..

==> Summation where i ranges from 0 to N-1( Summation where j ranges from 0 to N-1( 1 ) )

As Summation from lowerlimit to upperlimit of 1 is upperlimit - lowerlimit + 1 it goes as

==> Summation where i ranges from 0 to N-1( N-1-0+1 )

==> Summation where i ranges from 0 to N-1( N )

==> N * Summation where i ranges from 0 to N-1( 1 )

==> N * ( N-1-0+1 )

==> N * N

==> BigOh( N^2 )

Ok and the code OP showed should be similarly proved right? Like so :

Summation from i = 1 to N

Summation from j = x, where x = 2^i

Thus N * Summation from j = x, where x = 2^i = {1,2,4,8,16...}

If you look on wiki_summation. In the growth rate section it tells you that: Summation from i to N of c^i = THETA(c^n).

In our case c = 2, thus Summation from i to N of 2^i = THETA(2^n);

Thus N * Summation from j = x, where x = 2^i

= N * THETA(2^n)

= THETA(n*2^n)

Ok and the code OP showed should be similarly proved right? Like so :

Summation from i = 1 to N

Summation from j = x, where x = 2^iThus N * Summation from j = x, where x = 2^i = {1,2,4,8,16...}

If you look on wiki_summation. In the growth rate section it tells you that: Summation from i to N of c^i = THETA(c^n).

In our case c = 2, thus Summation from i to N of 2^i = THETA(2^n);Thus N * Summation from j = x, where x = 2^i

= N * THETA(2^n)

= THETA(n*2^n)

@firstPerson:

All the rules I have used are under section **"Some summations of polynomial expressions"** of your given article. And even after checking with the document you sent I am finding that I am on the right path and came up with right complexity for BigOh.But ya if its Theta (average) it may change. I do agree. But normally complexity analysis is done to set the upper limit so I have concentrated on BigOh notation only. Do check your calculations once.Thank You.

Ok and the code OP showed should be similarly proved right? Like so :

Summation from i = 1 to N

Summation from j = x, where x = 2^iThus N * Summation from j = x, where x = 2^i = {1,2,4,8,16...}

If you look on wiki_summation. In the growth rate section it tells you that: Summation from i to N of c^i = THETA(c^n).

In our case c = 2, thus Summation from i to N of 2^i = THETA(2^n);Thus N * Summation from j = x, where x = 2^i

= N * THETA(2^n)

= THETA(n*2^n)

"Summation from i to N of c^i" is exactly what the code does, you're confusing the second loop with something that it is not :). Maybe you're considering "Summation from j = x, where x = 2^i" as O(2^N) and summing that N times, which does indeed result in O(N * 2^N), but a better bound can be found. Here's a picture that might clear things up: