Accidentally Quadratic

Code is accidentally quadratic when it looks $O(n)$ but is actually $O(n^2)$, because a linear operation is nested inside another linear loop. From ECE459 L09.

Why?

Most real problems are linear at their core: take an item, process it, move on. The bug shows up when you stack two linear things and don’t notice the multiplication. A single insert is cheap, but doing $n$ of them when each one scans the whole structure is quadratic.

L09’s example. Rust’s hash tables used Robin Hood hashing, which is open addressing with linear probing where items further from their intended bucket get swapped forward.

Resizing copies every item into a new, larger table. That is fine early on, but as the new table fills, each insert has to linear-probe further to find a free slot. So you get a linear probe happening inside a linear loop over all items, which is quadratic.

One-line framing: given many elements to insert into an almost-full hash table, runtime becomes quadratic because each insert does a linear probe.

Related

• Profiling