10.13 Performance

Time Complexity

Operation	Complexity	Notes
`l[i]` (index)	O(1)	Direct memory offset
`l.append(x)`	O(1) amortized	Spare capacity absorbs most calls (see 10.1 Introduction to Lists)
`l.insert(0, x)`	O(n)	Every existing element must shift right
`l.pop()`	O(1)	Removing the last element
`l.pop(0)`	O(n)	Removing the first element — everything shifts left
`x in l`	O(n)	Linear scan
`len(l)`	O(1)	Length is cached, not recounted
`l.sort()`	O(n log n)	Timsort

Memory

A list’s per-object overhead plus its spare capacity (see 10.1 Introduction to Lists) means it typically uses somewhat more memory than an equivalent tuple — worth considering for very large, unchanging collections (see 5.4 Sequence Data Types).

`append()` vs. `insert()`

append() is O(1) amortized because it only ever touches the end. insert() at any position other than the end is O(n), because every following element must shift over. Prefer append() whenever order allows it.

# Fast: O(1) amortized per call
results = []
for item in data:
    results.append(item)

# Slow: O(n) per call -- O(n^2) overall for n items
results = []
for item in data:
    results.insert(0, item)

Quick Interview Answer

“The list operations worth knowing cold: indexing and len() are O(1); append() and pop() (from the end) are O(1) amortized because they only touch one end of the underlying array; insert(0, x) and pop(0) are both O(n) because everything else has to shift; membership testing (in) is an O(n) linear scan; and sort() is O(n log n), using Timsort. The practical consequence that shows up constantly in real code: building a list by repeatedly inserting at the front is O(n²) overall, while appending and reversing (or just appending in the right order to begin with) is O(n).”

Common Mistakes

Using l.insert(0, x) in a loop to build a list in reverse order, turning an O(n) job into O(n²) — append in the correct order, or append and reverse once at the end.
Checking x in large_list repeatedly in a hot path instead of converting to a set once for O(1) average-case membership tests.
Assuming len(l) re-scans the list — it’s O(1), since the length is cached on the object, not recomputed on each call.