The repeated checks in the loop will be reduced significantly in cost due to branch prediction.
Adding an item to each end of the array induces two problems:
- Adding to the beginning of the array will require all elements of the array to be shifted, and possibly a reallocation and cache miss (depending on implementation language).
- Adding to the end of the array will require traversing the array, potentially causing an extra cache miss.
Cache misses and reallocations are generally the highest performance costs to pay in computing today. O(x) alone is not sufficient to determine an algorithm's real-world performance.
Adding an item to each end of the array induces two problems:
- Adding to the beginning of the array will require all elements of the array to be shifted, and possibly a reallocation and cache miss (depending on implementation language).
- Adding to the end of the array will require traversing the array, potentially causing an extra cache miss.
Cache misses and reallocations are generally the highest performance costs to pay in computing today. O(x) alone is not sufficient to determine an algorithm's real-world performance.