I have two snippets of code that I am having a lot of trouble with finding the closed form Summations and time complexities for:

x=0;
for(i=1;i< pow(2,N); i = 2*i + 2){
for(j=1;j<N ; j++){
x=x+j;
}
}

and:

x=0;
for(i=1;i <= (2*n); i++){
for(j=1; j <= n; j++){
if(j<i) x=x+1;
}
}

Anyone have any idea how to solve those in closed form??

5
Contributors
4
Replies
7
Views
13 Years
Discussion Span
Last Post by swati poddar

Hi

If you want the big-Oh
then the first one is O(n^2) That what i calculate
if you want me to proof it i will But first i will ask my teacher about the first loop... i'm not sure about the first loop

the second O(n^2)

It can't be calculated, because Windows always wants its time slice right in the middle.

I have two snippets of code that I am having a lot of trouble with finding the closed form Summations and time complexities for:

x=0;
for(i=1;i< pow(2,N); i = 2*i + 2){
for(j=1;j<N ; j++){
x=x+j;
}
}

and:

x=0;
for(i=1;i <= (2*n); i++){
for(j=1; j <= n; j++){
if(j<i) x=x+1;
}
}

Anyone have any idea how to solve those in closed form??

Here's a hint for the first one.
The first step is to indent the code better so you can see what's happening.

``````for (i = 1; i < pow(2,N); i = 2*i+2)
{    for(j = 1; j < N; j+1)
x = x +j;
}``````

For each value of i the j loop does (N-1) additions, so the number of additions required is N-1)*the number of different values of i. The values of i that the program uses are 1, 4, 10,..22.. stopping at the biggest term that's < 2^N.
The k'th value of i is 3*2^(k-1)-2. (You figure out where I got this.) Then the biggest value of k for which this term is < 2^N is.....You finish up.

``````x=0;
for(i=1;i< pow(2,N); i = 2*i + 2)
{
for(j=1;j<N ; j++)
{
x=x+j;
}
}
``````

solution:

``````if N = 7
then i(i/p) = 1    i<128
i (o/p) = 4
i(i/p) = 4    i<128
i (o/p) = 10 (2*4 +2)
i(i/p) =10    i<128
i (o/p) = 22 (2*10+2)
i(i/p) =22    i<128
i (o/p) = 46 (2*22+2)
i(i/p) =46    i<128
i (o/p) = 94 (2*46+2)
i(i/p) =94    i<128
i (o/p) = 190 (2*94+2)
``````

so when we pass N = 7
in i loop we entering 6 times
that is (N-1) N=7

``````if N = 6
then i(i/p) = 1    i<64
i (o/p) = 4
i(i/p) = 4    i<64
i (o/p) = 10 (2*4 +2)
i(i/p) =10    i<64
i (o/p) = 22 (2*10+2)
i(i/p) =22    i<64
i (o/p) = 46 (2*22+2)
i(i/p) =46    i<64
i (o/p) = 94 (2*46+2)
``````

so when we pass N = 6
in i loop we entering 5 times
that is (N-1) N=6

``````if N = 5
then i(i/p) = 1    i<32
i (o/p) = 4
i(i/p) = 4    i<32
i (o/p) = 10 (2*4 +2)
i(i/p) =10    i<32
i (o/p) = 22 (2*10+2)
i(i/p) =22    i<32
i (o/p) = 46 (2*22+2)
``````

so when we pass N = 5
in i loop we entering 4 times
that is (N-1) N=5

``````if N = 4
then i(i/p) = 1    i<16
i (o/p) = 4
i(i/p) = 4    i<16
i (o/p) = 10 (2*4 +2)
i(i/p) =10    i<16
i (o/p) = 22 (2*10+2)
``````

so when we pass N = 4
in i loop we entering 3 times
that is (N-1) N=4

``````[1] Time complexity of x=1 is 1
[2] The time complexity for i loop will be (N-1)+1
(here +1 is for when it finally exiting the i loop).
[3] For j loop time complexity is (N-1)(N-1)+1
[4] Now for x=x+j time complexity is (N-1)(N-1)

Total = 1 + (N-1)+1 + (N-1)(N-1)+1 + (N-1)(N-1)

highest order is N^2 of (N-1)(N-1).
so time complexity is O(N^2).
``````

Edited by mike_2000_17: Fixed formatting

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.