Complexity & big-O on the BEAM

Big-O for a list is concrete: count how many cons cells an operation has to touch. Working at the head touches one cell, so it is O(1). Anything that needs the far end — length, append, last — touches every cell, so it is O(n). That single rule predicts the cost of every list function you will write.

Select an operation over a four-cell list and watch which cells light up. The number of touched cells is the complexity.

Cost is cells touched The cost cheat-sheet

Cost is cells touched

Prepend builds one cell and shares the rest, so only one cell is touched. Length and append have to reach the end, so they visit or copy all four. Same list, different cost — and the difference is visible in the cells.

The operation · select one

complexity: O(1) · touches: 1 cell at the head

If an operation can finish at the head, it is O(1); if it has to reach the end, it is O(n). Reading the cost is reading the cells — no benchmark required.

The cost cheat-sheet

The whole list-operation cost table follows from the cons shape. Prefer the head; treat anything at the end as linear, and reach for a different structure when you need the end to be fast — which is what the rest of F4 is about.

list = [1, 2, 3, 4]

[0 | list]        # prepend  · O(1)  — one new head cell
hd(list)          # head     · O(1)  — read the first cell
tl(list)          # tail     · O(1)  — the rest, shared
length(list)      # count    · O(n)  — walk every cell
list ++ [99]     # append   · O(n)  — copy the left list
List.last(list)   # last     · O(n)  — walk to the end

The idea

The cost of a list operation is how many cells it has to touch — one, or all of them.

In Elixir

O(1) at the head; O(n) for length, ++, and last.

That completes F4.01. Next module: F4.02 — Trees & traversals (in production), where the tail splits into two branches and an O(n) walk can become an O(log n) descent.

References

Primary sources for this lesson, and where it connects in the course.

Sources

List — Elixir documentation — cons-cell lists.
Efficiency Guide — Erlang/OTP documentation — complexity on the BEAM.
Okasaki, C. (1996). Purely Functional Data Structures. — the foundational text.