A completely reasonable-looking function

Checking a list for duplicates is something almost every real codebase needs somewhere. The straightforward version:

def has_duplicates(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

Compare every item against every other item. It's correct. It's also the shape of function that works fine in testing, on a small sample, and then quietly becomes the slowest part of a real pipeline once it's run against real, larger data.

What "quietly becomes the slowest part" looks like, measured

import time

for n in [1000, 2000, 4000, 8000]:
    data = make_unique_random_list(n)
    start = time.perf_counter()
    has_duplicates(data)
    elapsed = time.perf_counter() - start
    print(f"n={n}: {elapsed*1000:.1f} ms")

n=1000:    17.0 ms
n=2000:    70.7 ms
n=4000:   272.6 ms
n=8000:  1125.0 ms

The input size doubled three times, 1,000 to 8,000, a real 8x increase. The runtime didn't increase 8x. It increased roughly 66x, and each individual doubling step is worse than the last: 4.2x, then 3.9x, then 4.1x. That's not noise or measurement error, it's the actual shape of the function's real cost, and it's the signature of an algorithm whose work grows with the square of the input, not the input itself.

Why it grows like that

The inner loop runs once for every item already checked by the outer loop. For n items, that's roughly n * n / 2 total comparisons: 1,000 items means about 500,000 comparisons, 8,000 items means about 32,000,000. The input grew 8x. The actual number of comparisons the function has to do grew 64x, which is exactly why the measured runtime grew by roughly that much too. This is what "O(nĀ²)" describes: not a guess or an approximation, a real, direct relationship between input size and the amount of work the algorithm does, that happens to be quadratic.

The fix isn't a faster computer, it's a different algorithm

def has_duplicates_fast(items):
    seen = set()
    for item in items:
        if item in seen:
            return True
        seen.add(item)
    return False

One loop instead of two, backed by a real difference in how a set finds things: checking whether a value is already in a set doesn't require scanning through it, Python's set is a hash table, and a hash-based lookup takes roughly the same amount of time regardless of how many items are already in it.

n=1000:  naive =    17.0 ms   set-based =   0.07 ms   ratio =    240x
n=2000:  naive =    70.7 ms   set-based =   0.19 ms   ratio =    372x
n=4000:  naive =   272.6 ms   set-based =   0.33 ms   ratio =    822x
n=8000:  naive =  1125.0 ms   set-based =   0.76 ms   ratio =  1476x

The set-based version's runtime barely moves as n grows. The gap between the two approaches doesn't just stay large, it keeps widening, because one algorithm's cost scales with nĀ² and the other's scales with n. At small n the difference is invisible. At real production scale, it's the entire difference between a job that finishes in under a second and one that doesn't finish in a reasonable time at all.

Why this matters more than it sounds like it should

Nobody sets out to write an O(nĀ²) function on purpose. It happens by writing the obvious, correct-looking version of "check every item against every other item," which is a completely natural way to describe the problem in English and translates directly into nested loops. The bug isn't a logic error, the function returns the right answer every time, it's a cost problem that only shows up once the input is large enough to make it visible, which is usually well after the function has already shipped and passed every test written against small sample data.

The takeaway

If a job's runtime is growing faster than its input size, roughly quadrupling every time the data doubles is a real, checkable pattern, not a vague feeling, the algorithm itself is very likely the bottleneck, not the machine it's running on. The fix is usually a different data structure, here a set trading the ability to scan in order for near-constant-time membership checks, not a bigger server. Measuring the actual scaling behavior directly, the way the numbers above were produced, is what turns "this feels slow" into "this is provably quadratic, and here's why."