# Performance between looping twice seperately and looping within a loop

Just out of curiosity as I am coding, is there any performance difference between the two and it would be really great if someone knows how to prove it or calculate it.

Sorry if this question sounds stupid to you, hope you don't mind teaching newbs ;)

Thank you all!

-
Can you give us an example of what you mean? –  Mysticial Jun 12 '12 at 21:25
Which loops? :O –  user278064 Jun 12 '12 at 21:26
Speaking generally, the first is `O(n)` (linear time) and the second is `O(n^2)` (quadratic time). –  Matt Ball Jun 12 '12 at 21:26
Based on your description it seems like a difference between `O(2n)` and `O(n^2)` - please post some example code –  Tomasz Nurkiewicz Jun 12 '12 at 21:26
@TomaszNurkiewicz agreed, as per my earlier comment (but remember, `O(2n)` is `O(n)`). –  Matt Ball Jun 12 '12 at 21:27

It depends entirely on the loops. Here are some examples of `O(n^2)` running time:

``````1) Nested loops to n

for(i from 1 to n){
for(j from 1 to n){
...
}
}

2) Nested loops to n with the inner loop starting from i

for(i from 1 to n){
for(j from i to n){
...
}
}

3) Second loop iterates n^2 times since i == n

for(i from 1 to n){
...
}
for(j from 1 to i*n){
...
}

4) One loop up to n*n/50

for(i from 1 to n*n/50){
...
}
``````

Here are some examples of `O(n)` loops:

``````1) Simple loop

for(i from 1 to n){
...
}

2) Nested loop with constant iterations

for(i from 1 to n){
for(j from 1 to 5){
...
}
}
``````

Then you have the fact that better time complexities aren't always faster for small enough `n`, like the loop to `n*n/50`. If `n` is less than `8` (a positive int) then that loop won't iterate at all, so it will obviously be faster than a the Simple loop with `O(n)`, which will iterate exactly `n` times.

-
Interesting! I was just thinking of the very basic ones. Seems like loops can get a lot more interesting! –  lpaxionj Jun 13 '12 at 14:31
@Jerry I saw your comment on the question, and the difference between your two simple loops the time complexity. The two loops side by side is `O(n)` and the two loops nested is `O(n^2)` what that means is that there is a certain `n` where from that point onward the side by side loops will always take less time. If we assume that the contents of the loops are identical (and ignore the loop header) we can get an exact answer for this situation: –  Paulpro Jun 13 '12 at 15:59
The contents of the loop for the side by side ones execute exactly `2n` times and then contents of the nested loop execute exactly `n^2` times. So we can solve the equation `2n = n^2` for n. Divide both sides by `n` and you get `2 = n` (or `n = 2`). –  Paulpro Jun 13 '12 at 16:00
So when `n` is `2` both loops take the same time (4 iterations). It's easy to see that when `n` is `1` the `n^1` one is faster (1 iteration). the side by side loops have 2 iterations. When `n` is 0 they are both 0 iterations. But when `n` is anything larger than `2` then 2 side by side loops will be less iterations. Say `n` is 10. Then you'll get `20` iterations with the side by side loops, but `100` with the nested loops. The larger `n` gets away from `2` the bigger the gap. –  Paulpro Jun 13 '12 at 16:03

Generally speaking:

It could be `O(n + m)` if you've two distinct loops of different lengths (`n` and `m`).

``````for (int i = 0; i < n; i++) {}
for (int i = 0; i < m; i++) {}
``````

It could be `O(n * m)` if your looping within a loop.

``````for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
}
}
``````
-
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}