CODEWITHSUNDEEP
loopstime-complexitybig-o
MD TAHMID HOSSAIN
MD TAHMID HOSSAIN

Reputation: 1720

Why time complexicity of this code is O(n) instead of O(log n)

Following code's time complexity is O(n log n) I think for the outer loop log n but for the inner loop n. So, O(n logn )

x = n 
while ( x > 0 ) { 
    y = n 
    while ( y > 0 ) { 
        y = y - 1 
    } 
    x = x / 2 
}

But following code's time complexity is O(n)

x = n 
while ( x > 0 ) { 
    y = x 
    while ( y > 0 ) { 
        y = y - 1 
    } 
    x = x / 2 
}

Why is above code's time complexity is O(n)?

Upvotes: 0

Views: 43

Answers (1)

Barmar
Barmar

Reputation: 781340

Because the number of iterations of the inner loop is reduced by the same ratio as x is reduced. The total number of iterations will always be approximately 2n - 1 (it's exact when n is a power of 2, it deviates a bit for other numbers). Big-O ignores coefficients and lower-order components to the sum, so that's O(n).

For instance, when n == 16, the first iteration of the outer loop performs 16 iterations of the inner loop. The second iteration performs 8, then 4, and so on. So the total number is 16+8+4+2+1 == 31.

Upvotes: 1

Related Questions