CODEWITHSUNDEEP
algorithmloopsbig-otime-complexity
idude
idude

Reputation: 4912

Big O Notation for two non-nested loops

What would the Big O notation be for two for loops that aren't nested?

Example:

for(int i=0; i<n; i++){
   System.out.println(i);
}

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

Upvotes: 20

Views: 20917

Answers (5)

Palash Rathore
Palash Rathore

Reputation: 9

Assuming a scenario each loop runs up to n

So we can say the complexity of each for loop is O(n) as each loop will run n times.

So you specified these loops are not nested in a linear scenario for first loop O(n)+ second loop O(n)+ third loop O(n) which will give you 3O(n).

Now as we are mostly concentrating on the variable part of the complexity we will exclude the constant part and will say it's O(n) for this scenario.

But in a practical scenario, I will suggest you keep in mind that the constant factor will also play a vital role so never exclude them.

For example, consider time complexity to find the smallest integer from an integer array anyone will say it's O(n) but to find second largest or smallest of the same array will be O(2n).

But most of the answers will be saying it's O(n) where actually ignoring the constant. Consider if the array is of 10 million size then that constant can't be ignored.

Upvotes: 1

TheLostMind
TheLostMind

Reputation: 36304

It will be O(n) + O(n) ==> Effectively O(n) since we don't keep constant values.

Upvotes: 5

Luke Joshua Park
Luke Joshua Park

Reputation: 9795

Technically this algorithm still operates in O(n) time.

While the number of iterations increases by 2 for each increase in n, the time taken still increases at a linear rate, thus, in O(n) time.

Upvotes: 9

Salvador Dali
Salvador Dali

Reputation: 222481

Linear

O(n) + O(n) = 2*O(n) = O(n)

It does not matter how many non nested loops do you have (if this number is a constant and does not depends on n) the complexity would be linear and would equal to the maximum number of iterations in the loop.

Upvotes: 33

Atri
Atri

Reputation: 5831

It would be O(2n) because you run n+n = 2n iterations.

O(2n) is essentially equivalent to O(n) as 2 is a constant.

Upvotes: 5

Related Questions