CODEWITHSUNDEEP
complexity-theory
jesse10z
jesse10z

Reputation: 11

Big O complexity of for nested loop

I must find the Big O complexity for this loop: 

for(i=0; i<n; i++)
    for(j=0; j<n-i; j++)
        print(i)

I think it's O(n^2), but I'm not really sure. Can anyone help me?

Upvotes: 1

Views: 53

Answers (1)

rollstuhlfahrer
rollstuhlfahrer

Reputation: 4078

You are correct, the complexity is O(n^2).

  • The first loop (for(i=0; i<n; i++)) is pretty easy. That is O(n).

  • The second loop (for(j=0; j<n-i; j++)) is trickier: It is (theoretically) O(n - i).

When you combine those two, you will end up with:

O = n^2 - i*n

Since the Bit O notation only takes the largest factor, you simply remove the - i*n and end up with:

O(n^2)

Upvotes: 2

Related Questions