메모리에서 Big O로 설명된 어레이 (실제 벤치마크 포함)

This Loop Should Delete Three Items. It Deletes Two.

scores = [45, 30, 88, 92, 15, 67]

for score in scores:
    if score < 50:
        scores.remove(score)

print(scores)

Enter fullscreen mode Exit fullscreen mode

Read that and guess the output. Three values are under 50: 45, 30, 15. So the obvious guess is [88, 92, 67].

Run it, and Python prints [30, 88, 92, 67].

30 survives. Nothing crashed, no exception, no warning. The code just quietly kept a value it was explicitly told to remove.

Swap the language and the bug follows you:

const scores = [45, 30, 88, 92, 15, 67];

for (let i = 0; i < scores.length; i++) {
  if (scores[i] < 50) {
    scores.splice(i, 1);
  }
}

console.log(scores);

Enter fullscreen mode Exit fullscreen mode

Same input, same wrong survivor: [ 30, 88, 92, 67 ].

Two different languages, two different removal methods, the exact same failure. That’s not a coincidence. It’s what an array is underneath both of them, and Day 2 starts there.

What An Array Actually Is

Forget the syntax for a second. At the hardware level, an array is a promise: a single, unbroken block of memory, where every element sits the same distance apart.

That promise is what makes scores[3] fast. The computer doesn’t search for index 3. It calculates an address directly: start of the block, plus 3 times the size of one element, done. One arithmetic operation, one memory read. That’s the entire reason array access is O(1): it’s not clever, it’s just math.

Deletion breaks that promise, at least temporarily. Remove the item at index 0, and there’s now a gap at the front of an otherwise unbroken block. The only way to restore the promise (a single contiguous run with no holes) is to physically slide every element after the gap back by one position.

That slide is the whole story. It’s an O(n) memory move hiding behind a one-line method call, and it’s exactly what desynced the loop above.

Why The Loop Skips

Walk scores.remove(score) through what actually happens in memory, one step at a time:

1. The loop’s cursor sits at index 0. It reads 45, sees it’s under 50, and removes it.

2. Removing index 0 slides everything left by one slot. The value that used to be at index 1, 30, is now sitting at index 0.

3. The loop cursor doesn’t know that happened. It advances to index 1, as it always does.

4. Index 1 now holds 88, the value that used to be two slots over. 30 was never re-examined. It’s still in the array when the loop ends, because the loop moved past the exact slot it landed in.

The fix follows directly from the same mental model. Either walk the array backward, so every shift happens behind the cursor instead of into it:

scores = [45, 30, 88, 92, 15, 67]

for i in range(len(scores) - 1, -1, -1):
    if scores[i] < 50:
        scores.pop(i)

Enter fullscreen mode Exit fullscreen mode

or don’t mutate the array you’re iterating at all, build a new one instead:

scores = [45, 30, 88, 92, 15, 67]
scores = [s for s in scores if s >= 50]

Enter fullscreen mode Exit fullscreen mode

The second version is also the one worth defaulting to. It sidesteps the shifting problem entirely instead of just working around it.

Static Arrays vs. What You’re Actually Using

C’s int arr[10] is a static array: one fixed-size block, allocated once, that can never grow. Ask for an 11th slot and there’s no polite failure. You’re writing into memory that belongs to something else.

Python’s list and JavaScript’s Array aren’t that. They’re dynamic arrays: a static array under the hood, wrapped in logic that swaps in a bigger block once the old one fills up. Every .append() or .push() you’ve ever called was secretly asking “is there room?” before it ever touched memory.

That wrapping is why beginners get told arrays are O(1) to append to, and it’s mostly true, but “mostly” is doing real work in that sentence, covered next.

Every Core Operation, Rated

Operation Complexity Why 🟢 Access by index O(1) Direct address math, no searching 🟢 Append / pop at the end O(1)* No shift needed; *occasionally O(n) — grows past capacity, shrinks past half capacity, more below 🟠 Search (unsorted) O(n) No shortcuts — check every slot until found 🔴 Insert / delete at the start O(n) Every remaining element shifts by one 🔴 Insert / delete in the middle O(n) Same shift, just for a shorter stretch

The pattern in that table is the entire lesson: where in the array you operate matters as much as what operation you run. The end is cheap. The front is expensive. That’s not a Python or JavaScript quirk. It’s physics, the same physics that broke the loop above.

The Asterisk on “O(1) Append”

Dynamic arrays grow by over-allocating: when the backing block fills up, they don’t grab one more slot, they grab a noticeably bigger block and copy everything over. That copy is O(n), but it happens rarely enough that the average cost per append, over many appends, still comes out to O(1). That average has a name: amortized O(1).

“Rarely enough” isn’t hand-waving. CPython’s growth pattern is public, and it’s checkable from Python itself, since sys.getsizeof() reports the backing array’s real allocated size, not just the list’s length. Appending one item at a time and watching that number jump gives you the exact resize points, live, on CPython 3.12:

List length at resize Backing array size (bytes) Slots allocated 1 88 4 5 120 8 9 184 16 17 248 24 25 312 32 33 376 40

Between each row, appends are just writing into already-reserved space: genuinely O(1), no copying at all. The resize itself, on that one unlucky append, is O(n). Spread that occasional O(n) cost across all the free appends in between, and it averages out to O(1) per call.

Shrinking runs the same machinery in reverse, on a different trigger than most people guess. pop() doesn’t hand memory back the moment the list gets smaller: CPython only reallocates down once the length falls under half of what’s currently allocated, not the instant a single slot goes unused. Pop a 33-item list down to empty and the real shrink points, traced the same way with sys.getsizeof(), land at lengths 16, 11, 7, 5, 1, and 0. Compare that to the growth table above and the thresholds don’t mirror each other; growing and shrinking are governed by two separate rules sharing one function, not a single reversible curve.

V8 runs the same strategy for JavaScript arrays, over-allocating on growth instead of resizing one slot at a time. That’s why .push() gets the same amortized O(1) label .append() does.

One More Thing V8 Tracks That CPython Doesn’t

V8 keeps something called an array’s elements kind — a running classification of what’s actually in it: all small integers, mixed with floats, holding arbitrary objects, or containing gaps. V8’s own engineering blog lays out the mechanism: arrays built with actual gaps in them (skipped indices, or presized with new Array(n) and filled out of order) get marked holey, and every read from a holey array carries an extra check a gap-free (“packed”) array skips.

That transition only runs one direction: specific to general, packed to holey. It’s permanent. Fill every gap in a holey array later, and V8 still won’t reclassify it back to packed. The practical takeaway: build arrays in order, front to back, if you want V8 to keep every optimization available to it.

How much that actually costs in practice is genuinely inconsistent. A plain summation loop over a packed vs. a holey million-element array, benchmarked repeatedly on this machine, came back centered close to even, drifting up to roughly 13% either direction depending on the run, with no consistent winner. Real, but not the dramatic one-directional gap sometimes claimed for it online. The scripts to run that comparison yourself are in the attached zip.

The Benchmarks

Same rule as Day 1: no number below is estimated. Python 3.12 and Node.js 22, timed with time.perf_counter() and process.hrtime.bigint(), each operation paired with its opposite (append then pop, insert then remove) so the array’s size stays constant across the whole run.

End of the array: append / pop

n Python append (ns) Python pop (ns) Node push+pop (ns, combined) 1,000 44.9 31.0 10.0 10,000 31.4 31.0 1.9 100,000 32.1 30.9 2.0 1,000,000 31.7 34.6 1.7

Flat across four orders of magnitude, in both languages. That’s the empirical signature of O(1). The Node numbers look almost too fast to be real; that’s V8’s JIT compiling this exact push-then-pop pattern more aggressively the longer the process runs, not a language-superiority result. Treat the flatness as the finding, not the specific nanosecond count.

Start of the array: insert / delete

n Python insert(0) (µs) Python pop(0) (µs) Node unshift (µs) Node shift (µs) 1,000 0.26 0.12 0.14 0.12 10,000 2.60 1.84 1.85 0.13 100,000 24.77 17.97 18.65 18.39 1,000,000 364.64 342.58 362.43 348.51

10x the input keeps landing close to 10x the time, in every column. That’s the same linear signature the O(n) search benchmark showed on Day 1, now showing up for a different operation entirely. (Node’s shift at n=10,000 reads oddly low next to its neighbors — at that size the fixed cost of the function call itself is still competing with the shift cost, so the line hasn’t straightened out yet. It does by 100,000.)

Both scripts behind every number in this post (the Python and Node versions, plus the resize-point tracer and the packed/holey comparison) are packaged in arrays-ops-benchmark.zip, attached to this post.

Back to the Bug

The loop at the top of this post wasn’t a trick question. It’s the single most common way arrays bite working developers, in any language that has them, and it only looks mysterious until you’ve internalized what deletion actually costs.

Once you know an array is a contiguous block, and that removing from the middle means physically sliding everything after it, the loop’s behavior stops being surprising. It’s not broken. It’s doing exactly what shifting a block of memory always does. The bug was ever expecting the cursor to notice.

Try it yourself before the next post: take the backward-iteration fix above, and instead of removing values under 50, remove every duplicate value from a list, keeping just the first occurrence of each. Same shifting mechanics, one extra piece of state to track. It’s a good gut-check for whether the mental model actually stuck.

Originally published on ZyVOP

💡 For more articles like this, subscribe to the ZyVOP newsletter!