complexity for a nested loop with growing internal loop

Question

I am confused to the time complexity of this piece of code and the logic used to find it.

void doit(int N) {
    for (int k = 1; k < N; k *= 2) { <----I am guessing this runs O(logN)
           for (int j = 1; j < k; j += 1) { <------I am not sure how this one works.
       }
    }
}

I have already tried solving it out by hand writing it out. But, I still don't understand it.

Thank you for your time.

EDIT:

Adding another question to it. Same concept, different format.

void doit(int N) {
    int j, k; //I ended up getting this answer to be O(n^(n/2)) But then I was stuck after that...is that even the right answer?
    for (k = 1; k < N / 2; k += 1) {
       for (j = k; j < 2 * k; j += 1) [
             x[j] = x[j-k] + x[j];//This doesn't really matter
        }
    }
}

amit · Accepted Answer · 2012-12-11 11:05:54Z

8

The total complexity is actually O(N)

Claim: For each k you have k inner loop iterations. (convince yourself why it is correct)

Denote the number of total inner loops iterations by T(N), and let the number of outer loops be h.
This means we have:

T(N) = 1 + 2 + 4 + ... + 2^h 
     < 2 * 2^h               (1)
     = 2^(h+1)     
     = 2^(logN + 1)          (2)
     = 2^(log(2N))   
     = 2N

(1) From sum or geometric series
(2) Note that the equality 2^(h+1) = 2^(logN + 1) is because h = logN, we have (as you said) logN outer loop iterations.

edited Dec 11, 2012 at 11:05

answered Dec 11, 2012 at 11:00

amit

179k27 gold badges245 silver badges348 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Mathew Kurian Over a year ago

I added another question...same format but different loop growths, I am stuck on finding the answer here. Can you please help me out? thank you in advance

amit Over a year ago

@bluejamesbond: You should ask new questions as new quetions, and not edit. However - Note that in the second case the number of inner loops iterations T(n) = (2-1) + (4-2) + (6-3) + ... (N-N/2) = 1 + 2 + 3 + 4 + .... + (N/2) which is O(N^2) from sum of arithmetic progression.

Mathew Kurian Over a year ago

yes I will. woahh! how did you figure that out? how do you learn this?

amit Over a year ago

@bluejamesbond: some math background before starting to learn algorithms is helpful, but mostly - experience.

Mathew Kurian Over a year ago

are there any online practice problems where i can just go down a list of them and see if i have the correct answer? or similar.

|

Collectives™ on Stack Overflow

complexity for a nested loop with growing internal loop

1 Answer 1

6 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related