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

5
Contributors
13
Replies
14
Views
6 Years
Discussion Span
Last Post by gashtio

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

Edited by csurfer: n/a

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

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)

Edited by firstPerson: n/a

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

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

@CSurfer
What is the runtime of this :

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

Edited by firstPerson: n/a

@CSurfer
What is the runtime of this :

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

@firstPerson:

Its BigOh(N^2)

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

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

Edited by csurfer: n/a

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: