Why Quadratic Algorithms Fall Apart at Scale
Interview prep and real engineering share at least one concern: the difference between an algorithm that scales gracefully and one that collapses under load. The classic example is intersecting two lists of numbers — returning values that appear in both. A naive double loop works fine on small inputs but becomes unusable surprisingly fast.
The Obvious Solution Is Often Quadratic
The straightforward approach checks every element of the first list against every element of the second:
import sys
# the actual code
def intersection(list1, list2):
result = []
for x in list1:
for y in list2:
if x == y:
result.append(y)
return result
# some boilerplate so that we can run it from the command line on lists of
# different sizes
def run(n):
# make 2 lists of n+1 elements
list1 = list(range(3, n)) + [2]
list2 = list(range(n+1, 2*n)) + [2]
# intersect them and print out the result
print(list(intersection(list1, list2)))
# Run with the program's first command line argument
run(int(sys.argv[1]))
With two lists of size n, the inner comparison runs n^2 times — hence the name quadratic.py. That mathematical property (x^2 is a quadratic function) is exactly what makes the slowdown so steep.
Measuring the Slowdown
Running this code against progressively larger inputs shows what quadratic growth actually feels like. With small lists, the timings look unremarkable:
$ time python3 quadratic.py 10
[2]
real 0m0.037s
$ time python3 quadratic.py 100
[2]
real 0m0.053s
$ time python3 quadratic.py 1000
[2]
real 0m0.051s
$ time python3 quadratic.py 10000 # 10,000
[2]
real 0m1.661s
Still under two seconds, so nothing seems wrong. But bump the inputs to 100,000 elements each, and the wait becomes painful:
$ time python3 quadratic.py 100000 # 100,000
[2]
real 2m41.059s
That burst from 1.6 seconds to 160 seconds is the signature of quadratic behavior: 10x more data costs roughly 100x more time. Scaling to a million elements would mean waiting around three hours. Even this contrived example demonstrates why quadratic algorithms become a production hazard once input sizes grow.
A Linear Alternative Using a Hash Set
The fix is to convert the first list into a hash set, then do a single pass over the second list checking membership. The code below avoids overly idiomatic Python so the logic stays readable:
import sys
# the actual algorithm
def intersection(list1, list2):
set1 = set(list1) # this is a hash set
result = []
for y in list2:
if y in set1:
result.append(y)
return result
# some boilerplate so that we can run it from the command line on lists of
# different sizes
def run(n):
# make 2 lists of n+1 elements
list1 = range(3, n) + [2]
list2 = range(n+1, 2*n) + [2]
# print out the intersection
print(intersection(list1, list2))
run(int(sys.argv[1]))
Two changes make the difference: building set1 from list1, and replacing the nested loops with one loop. The running time now scales linearly — doubling the input doubles the work rather than quadrupling it.
Linear Scaling in Practice
Benchmarks on the same machine confirm the improvement. The linear version handles lists from 10 up to 10,000,000 elements without complaint — sizes that would have brought the quadratic version to a crawl at 100,000:
$ time python3 linear.py 100
[2]
real 0m0.056s
$ time python3 linear.py 1000
[2]
real 0m0.036s
$ time python3 linear.py 10000 # 10,000
[2]
real 0m0.028s
$ time python3 linear.py 100000 # 100,000
[2]
real 0m0.048s <-- quadratic.py took 2 minutes in this case! we're doing it in 0.04 seconds now!!! so fast!
$ time python3 linear.py 1000000 # 1,000,000
[2]
real 0m0.178s
$ time python3 linear.py 10000000 # 10,000,000
[2]
real 0m1.560s
Even a list of 10 billion elements would be plausible from a time perspective (roughly 420 seconds, since it's 100x larger than the 4.2-second benchmark). The real blocker there is memory, not speed:
$ time python3 linear.py 10000000000
Traceback (most recent call last):
File "/home/bork/work/homepage/linear.py", line 18, in <module>
run(int(sys.argv[1]))
File "/home/bork/work/homepage/linear.py", line 13, in run
list1 = [1] * n + [2]
MemoryError
real 0m0.090s
user 0m0.034s
sys 0m0.018s
That's a separate concern outside this discussion, but worth remembering when designing for very large datasets.
Why the Membership Check Is Constant Time
The critical line in the fast version is the condition inside the loop:
def intersection(list1, list2):
set1 = set(list1) # this is a hash set
result = []
for y in list2:
if y in set1:
result.append(y)
return result
The check if y in set1 performs the same whether set1 holds a thousand elements or ten million. That's because set1 is a hash set — a hashmap with only keys — and hashmap lookups are effectively instantaneous regardless of size. The basecs series on hash tables and hash functions explains the mechanics behind this constant-time behavior.
Quadratic Code Creeps Into Real Systems
This isn't just an interview artifact. Accidental quadratic behavior shows up in production code often enough that Nelson Elhage documents real-world cases of performance bugs caused by exactly this pattern.
The insidious part is how harmless quadratic logic seems at small scales. A thousand elements completes so quickly you never notice the problem. Feed it a million, though, and hours evaporate. That's why it pays to recognize the pattern and reach for a hashmap when the easy linear alternative exists.
When the "Slow" Method Wins
Performance engineering has nuance, though. In constrained environments — embedded systems, for example — the constant-factor overhead of building a hashmap can outweigh its asymptotic advantage on small inputs. Friends working on such systems have told me this comes up regularly. A useful illustration is this benchmark showing linear search beating binary search on arrays of up to 100 elements. The right choice always depends on the actual data sizes you'll encounter.
Hashmaps aren't literal magic — the math behind their constant-time lookups is teachable and fascinating. But the way a single data structure converts an unusable program into one that handles millions of items smoothly is about as close to magic as engineering gets.
