CODEWITHSUNDEEP
javafor-looptime-complexitylogarithm
Prashant Meena
Prashant Meena

Reputation: 1

Time complexity of Nested loop with dependent variable and logarithmic increment

what is the time complexity of this loop, O(N) or O(N (logN ))

also can you explain how you deduced

for (int i = 1; i <= n;  i *= 2) {   
    for (int j = 0; j < i; j++) {
        // Statement(s) that take(s) constant time
   }
}

i have an explanation but it feels wrong

explanation on educative.io

Upvotes: 0

Views: 1081

Answers (1)

PiNaKa30
PiNaKa30

Reputation: 674

I think you are confused because of the statement O(n + log(n)), as you thought that the outer loop runs logN times and inner loop runs N times so the answer should be O(NlogN). You are wrong here because the inner loop doesn't run N times, it only runs i times as explained. Now when you sum all the i over outer loop, you will get that 2*2^k - 1 statement. This will come out to be order of N as given in the explanation.

Upvotes: 1

Related Questions