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

[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

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