CODEWITHSUNDEEP
algorithmbig-o
Joseph
Joseph

Reputation: 357

If a nested for-loop has two different starting iterations, is the time complexity still O(n^2)?

If we have a nested for-loop like the one below:

for (int i=0; i < n; i++){
    for (int j=1; j < n; j++){
        // do something       
     }
}

Would the worst-case complexity be O(n^2) even though j (at worst) will always search n-1 of the array/list?

Upvotes: 1

Views: 68

Answers (2)

גלעד ברקן
גלעד ברקן

Reputation: 23945

The answer depends on how the iterations are defined. To take your example,

n*(n-1) = n^2 - n

but complexity analysis defers to the largest exponent since the smaller ones become insignificant as n tends to infinity.

However, if you would define a second iteration as:

for i = 0 to n:
  for j = (n-1000000) to n:

we would have an O(n * constant) or O(n) complexity.

Upvotes: 0

Bill the Lizard
Bill the Lizard

Reputation: 405955

You're only subtracting a constant, so the complexity of the inner loop still grows with n, so that loop is O(n). Both nested together are O(n^2).

Upvotes: 2

Related Questions