Constant Size Array Creation Within For Loop Time Complexity

Question

I am relatively new to learning Big-O Notation and was hoping someone could shed some light on a question that, while simple, has been nagging me. This question arose in a different context than the one then I will show below, but it addresses the same concern. Let's say that we had an input array of N elements, and a for loop that will loop over these N elements. Within the loop, however, we perform some constant-size array creations of size 2. Also, please disregard the triviality of this operation, it helps simplify the original problem on which I was working.

for (let i = 0; i < array.length; i++) {
   const newArray = [array[i], array[i+1]];

   // Do some other stuff...
}

I am thinking that the complexity of this operation would be O(2), but we perform this operation N times, resulting in O(2N), or O(N) since we disregard constants. And although we do allocate memory on each loop, it gets cleaned up between each subsequent iteration and then once upon termination of the loop, so the space complexity would remain O(1). Am I on the right track? Thanks so much!!

"although we do allocate memory on each iteration, it gets cleaned up in between, so the space complexity would remain O(1)." - maybe. It depends on what the "other stuff" code is doing with the newArray. — Bergi
– Bergi, Commented Jul 7, 2022 at 1:10

ggorlen · Accepted Answer · 2022-07-07 00:26:33Z

2

O(N) since we disregard constants.

Yep: this is the time complexity.

And although we do allocate memory on each loop, it gets cleaned up between each subsequent iteration and then once upon termination of the loop

Not necessarily--garbage collection probably won't occur exactly at each loop. The data goes out of scope but GC is usually batched. It's an implementation detail that complexity theory disregards.

I assume also that you're not pushing this array onto another array or anything that'd still reference it after the loop ends. That'd change the function's space complexity.

the space complexity would remain O(1).

Yep.

Even though space complexity looks good, the repeated memory allocations in a potentially hot loop may be expensive on a real workload, so you can't necessarily disregard this allocation completely. O(1) is not a guarantee that you don't have a performance problem, only that as n increases, the cost stays the same. A function that allocates a single array of a fixed size of 1 million is still O(1).

But I wouldn't worry prematurely until you see a real performance problem and have successfully identified this as a bottleneck through profiling. Some compilers might be able to optimize this into separate variables to avoid the allocation.

answered Jul 7, 2022 at 0:26

ggorlen

59.3k8 gold badges119 silver badges173 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Griffin Baker Over a year ago

Thank you! So the proper way to explain the constant space complexity would be the line contained within your answer where you said, "as n increases, the cost stays the same". Therefore, even if we don't GC the array due to compiler-level implementation details, that is not really a detail that we would speak to in Big O analysis? Just that every time we loop over the array we perform this constant space complexity operation that remains constant as N increases?

ggorlen Over a year ago

Whether the array is GC'd every loop or batched is irrelevant to computing big O, which doesn't factor in runtime conditions like cache friendliness, GC, resource contention, scheduling, speculative execution, etc. Big O is a scalability heuristic that only looks at the logical properties of an algorithm on paper, not the compiler, processor or language runtime and environment it might execute in.

ggorlen Over a year ago

The problem with Big O is that people assume it's the end of the story with performance, forgetting that constant factors are often a huge part of performance. That's why I suggest that it may be a bad idea to allocate this array even though Big O gives it the A-OK.

Griffin Baker Over a year ago

Ok gotcha, thank you. It seems that although the cost may not grow, like you said, that does not mean the cost may not be large / unnecessary.

Collectives™ on Stack Overflow

Constant Size Array Creation Within For Loop Time Complexity

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related