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!!
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.