Arrays and Time Complexity

Build the mental model

An array — and a Python list under the hood — stores its elements in one contiguous block of memory, back to back with no gaps. That layout is what makes `list[i]` an O(1) operation: the runtime doesn't search for the i-th element, it computes its exact memory address directly as `base_address + i * element_size` and jumps straight there, one arithmetic step regardless of whether the list holds 10 or 10 million items. That same contiguous layout is what makes inserting or deleting at the front expensive. If you insert a new element at index 0, every existing element has to physically shift one slot to the right to make room and preserve the contiguous, gapless layout — an operation touching all n existing elements, so it costs O(n). The same is true in reverse for deleting the first element: everything after it shifts left by one. This is a real trade-off, not an accident of a bad implementation: the very property that gives you constant-time random access (tight, contiguous packing) is the same property that forces a shift on every front insertion or deletion.

Connect it to a real scenario

The Tutorial Platform stores each course's lessons as an ordered list, so jumping straight to 'lesson 5 of chapter 2' is an O(1) index lookup, no matter how many lessons the course has. But if an instructor ever needed to insert a brand-new lesson at the very front of that list — say, a new prerequisite lesson 0 — every other lesson's position would have to shift by one, an O(n) operation across the whole course. That's exactly the kind of trade-off this course revisits later when linked lists and other structures offer a cheaper way to insert at the front.

Arrays/lists store elements in contiguous memory, so index access list[i] is O(1) via direct address math
Inserting or deleting at the front is O(n) because every following element must shift one slot
This is a structural trade-off, not a bug — contiguous packing is what enables both the O(1) access and the O(n) shift

Try the working example

python

lessons = ['intro', 'variables', 'loops', 'functions', 'recursion']

# Index access: O(1) -- jumps straight to the memory slot, no matter list size
print('Lesson at index 2:', lessons[2])

# Insert at front: O(n) -- every existing element shifts one slot right to make room
lessons.insert(0, 'prerequisites')
print('After front insert:', lessons)

You should see

Prints 'Lesson at index 2: loops' from a constant-time index lookup, then prints the list with 'prerequisites' shifted into position 0 and every other lesson pushed one slot right.

5-minute try-it

Write a small timing experiment: build a list of 100,000 items, then time 10,000 calls to `list.insert(0, x)` versus 10,000 calls to `list.append(x)`. Explain the timing difference using what you learned about shifting.

One important caution

Assuming all list operations are O(1) because 'list access is O(1)' — access by index is O(1), but insert/delete at the front (or anywhere but the end) is O(n) because of the required shift.

Repeatedly calling `list.insert(0, x)` inside a loop to build a list in order, not realizing each call is O(n), turning what looks like an O(n) loop into an accidental O(n²) algorithm.

Python Wiki — Time Complexity — Data Structures & Algorithms