Do multiple loops have same complexity as nested loops?

Question

This for loop has a complexity of O(n)

for ($i=0; $i < $arrCount - 1; $i++) { }

And this 2 nested for loops have a complexity of O(n^2)

for ($i=0; $i < $arrCount; $i++) { 
  for ($j=0; $j < $arrCount; $i++) { 
  }
}

But what if I did 2 for loops inside a function and they just folowed each other, no nesting

for ($i=0; $i < $arrCount; $i++) { 
}
for ($i=0; $i < $arrCount; $i++) { 
}

Would the function still be executed in O(n) ?

Answer 1

Yes.

Nested loops means that the outer loop will execute the inner one completely for each iteration (of the outer). This means O(n^2) in your case, because for each i from 0 to n we do n operations.

i = 0 => inner loop runs n iterations
i = 1 => inner loop runs n iterations
...
i = n - 1 => inner loop runs n iterations

n iterations n times means n^2 total iterations, so O(n^2).

Your 2 loops without nesting will each iterate n times, for a total of 2n times. Big-oh ignores constants, so 2n = O(n).

Since they are not nested, the number of times each one runs will not depend on the other. So you add the number of iterations, not multiply them.