4 / 8 Typing & Performance

Why Append Beats Concatenation

Both functions build the same list of n integers:

def build_a(n: int) -> list[int]:
    result = []
    for i in range(n):
        result.append(i)
    return result

def build_b(n: int) -> list[int]:
    result = []
    for i in range(n):
        result = result + [i]
    return result

Select all statements below that are true.

A

append's amortized O(1) behavior is guaranteed by the Python language specification, so every conforming implementation (CPython, PyPy, Jython) must over-allocate the same way.

B

build_a runs in O(n) total. CPython's list implementation over-allocates extra capacity whenever it grows, so most calls to append just write into already-reserved space instead of reallocating, making each append amortized O(1).

C

build_b runs in O(n^2) total. result + [i] builds a brand-new list and copies every existing element into it, on every one of the n iterations, so the copy costs sum to 1 + 2 + ... + n.

D

Both functions have the same asymptotic complexity, because list concatenation with + is just append called once per element under the hood.