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);
}

回答1:

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.

回答2:

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.

回答3:

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

回答4:

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.

回答5:

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.