Two Loops Divided by One Loop, is it okay?

user_8625533 0
Viewed 105

Below is a loop for two functions:

const foos = [1, 2, 3, 4, 5];

for ( let foo of foos ) {
  func1(foo);
  func2(foo);
}

I want to split it in two. Because of the semantic separation of the code. 

const foos = [1, 2, 3, 4, 5];

for ( let foo of foos ) {
  func1(foo);
}

for ( let foo of foos ) {
  func2(foo);
}

Leaving aside why I should do this, I am wondering if performance is degraded. In both cases, it's okay because it's O (n), right?

algorithm performance
2 Answers

This change does not affect time complexity. So, yes, assuming func1 and func2 are both O(1), then your time complexity is still O(n) (where n = len(foos)).

What could concern you though is that the 2 code snippets are not the same. Depending on your implementation of func1 and func2 you could get different result.
While first one does:

func1(1);
func2(1);
func1(2);
func2(2);
...

The second one does:

func1(1);
func1(2);
...
func2(1);
func2(2);
...

Intuitive explanation:
You changed from: O(n * (1 + 1)) = O(n * 2) = O(2n) = O(n)
operations to: O((n * 1) + (n * 1)) = O(n + n) = O(2n) = O(n).

user_55216700

Although it may not seem the case, iterating over a list has a cost. This is because we must repeatedly call a .next() on the list to retrieve the next item. For an array, it is going to be constant time, but for other enumerable structures, it may cost more depending on how the data is stored (like a hashmap for example).

Let us say the cost of enumerating is f(N) where N is the size of the collection. Let us assume for this example that func1 and func2 perform in constant time k.

The complexity of both is the same: O(N*f(N)+N*k)=O(N*f(N))

However, the true cost is different. You need to do an additional N*f(N) operations. Going for one loop as opposed to two may save you some noticeable time depending on f(N), but the overall complexity will stay the same.

user_94533110
Related