algorithm - Do multiple loops have same complexity as nested loops? -

this loop has complexity of o(n)

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

and 2 nested loops have complexity of o(n^2)

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

but if did 2 loops inside function , folowed each other, no nesting

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

would function still executed in o(n) ?

yes.

nested loops means outer loop execute inner 1 each iteration (of outer). means o(n^2) in case, because each i 0 n n operations.

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

n iterations n times means n^2 total iterations, o(n^2).

your 2 loops without nesting each iterate n times, total of 2n times. big-oh ignores constants, 2n = o(n).

since not nested, number of times each 1 runs not depend on other. add number of iterations, not multiply them.

Guide