Why O(n²) Will Hurt You · Data Structures & Algorithms

Ch 1 · Thinking Like a Computer Scientist — card 3 of 3.

A loop inside a loop usually means O(n²) — and that scales badly. With 1,000 items that is 1,000,000 steps; with 1,000,000 items it is a trillion. The code below finds a duplicate two ways so you can feel the difference.

# ❌ Slow: O(n²) — compares every pair
def has_duplicate_slow(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

# ✅ Fast: O(n) — remembers what it has seen using a set
def has_duplicate_fast(items):
    seen = set()
    for item in items:
        if item in seen:      # checking a set is O(1)
            return True
        seen.add(item)
    return False

print(has_duplicate_fast([3, 1, 4, 1, 5]))  # True