CODEWITHSUNDEEP
big-o
Bauer
Bauer

Reputation: 159

Are two (non nested) "for loops" iterating over the same size array of n = O(2n)

for example if we have 

public void search(){
 for (int i=0; i<n; i++){
      .............
     }

 for (int j=0; j<n; j++){
        .............
    }
 }

would search() be O(n) + O(n) = O(2n) ?

Upvotes: 1

Views: 398

Answers (3)

return true
return true

Reputation: 7916

Yes, the time is linear in n, but because constant factors are not interesting in O-notation, you can still write O(n). Even if you had 10 consecutive for-loops from 1 to n, it would still be O(n). Constant factors are dropped.

Edit (answer to your comment):

If i, n and k are independent, yes, it would be O(k + (n-i)). But you could simplify it if you for example know that k = O(n). (e.g. k ≈ n/2). Then you could write it as O(n - i) (because in O(2n - i), the 2 is dropped).

If i and k are both linearly dependent on n, it would even be O(n).

Upvotes: 2

Amadan
Amadan

Reputation: 198446

Big-O notation expresses time or space complexity. It does not measure time or space directly, it measures how the change in number of elements impacts time or space. While two loops are certainly slower than one, they both scale exactly the same: in direct proportion to n. That is what O(n) means.

(Slight simplification here, it does not account for why O(n^2 + n) = O(n^2), for example, but it should suffice for the matter at hand.)

Upvotes: 0

dramzy
dramzy

Reputation: 1429

Yes, this is O(2n) which is equivalent to saying it is O(n), the coefficient doesn't matter really.

Upvotes: 0

Related Questions