CODEWITHSUNDEEP
performanceloops
lpaxionj
lpaxionj

Reputation: 175

Performance between looping twice separately and looping within a loop

Is there any performance difference between looping twice separately and looping within a loop? How to prove it or calculate it?

Upvotes: 0

Views: 137

Answers (2)

user278064
user278064

Reputation: 10170

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++) {
   }
}

Upvotes: 1

Paul
Paul

Reputation: 141829

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.

Upvotes: 1

Related Questions