CODEWITHSUNDEEP
calgorithmcomplexity-theorybig-o
Mathew Kurian
Mathew Kurian

Reputation: 6039

complexity for a nested loop with growing internal loop

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

Upvotes: 2

Views: 274

Answers (1)

amit
amit

Reputation: 178431

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.

Upvotes: 8

Related Questions