Big-Oh Notation question

[pandaEater]

I've been working on getting the Big-Oh notation for this code segment a couple days now and I can't figure it out. I've most likely come across the right answer but I can't convince myself it's right. What's the Big-Oh notation for the following code and how do you arrive at that answer?

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

My work so far:
inner loop: executes x+1 times ; outer loop: n-2 times
therefore,
Summation of x+1, where x = 2^n, from i = 0 to n-2 gives the amount of executions for the inner for loop

I'm not sure how to convert the summation of 2^n to a form where I can get the Big-Oh

[csurfer]

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 :)

[arkoenig]

==> (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).

[mrnutty]

Are you guys sure about that runtime?

The first loop runs n times. And for each n, it runs 2^n. Thus the total runtime is O(n*2^n)

[pandaEater]

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!

[mrnutty]

>>Summation of 2^i + 1 from i = 0 to n-2.

That shows right there that its O(n*2^n);

[csurfer]

>>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.

[mrnutty]

@CSurfer
What is the runtime of this :

for i = 0 to N - 1
 for j = 0 to N - 1

[csurfer]

@CSurfer
What is the runtime of this :

for i = 0 to N - 1
 for j = 0 to N - 1

@firstPerson:

Its BigOh(N^2)

[mrnutty]

@firstPerson:

Its BigOh(N^2)

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.

[csurfer]

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 )

[mrnutty]

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)

[csurfer]

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)

@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.

[gashtio]

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)

"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: