Strange time complexity problems... help!

[theoddmonkey]

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

[abu_sager]

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)

[Real-tiner]

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

[murschech]

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.

[swati poddar]

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