Big-O intuition — what the notation is actually telling you

Big-O isn't a count of operations, it's a growth rate. Once that clicks, the whole hierarchy — O(1), O(log n), O(n), O(n log n), O(n^2) — stops being memorized trivia.

Beginner

3 min read

It's a shape, not a number

O(n) doesn't mean "n operations." It means: if you double the input size, the work roughly doubles. O(n^2) means doubling the input roughly quadruples the work. Big-O describes how the cost grows as input grows, stripped of constant factors and lower-order terms — which is exactly why an O(n) algorithm with a slow constant factor can genuinely be faster than an O(log n) algorithm in practice for small, realistic input sizes, even though the log one "wins" as n grows without bound.

The hierarchy, with what actually changes at each step

Complexity	Doubling n does this to the work	Concrete example
O(1)	Nothing — stays the same	Array index access, hash map lookup (average case)
O(log n)	Adds one more step	Binary search on a sorted array
O(n)	Doubles	A single pass through a list
O(n log n)	Slightly more than doubles	Efficient comparison-based sorting (merge sort, quicksort average case)
O(n^2)	Quadruples	Nested loop comparing every pair, naive bubble sort
O(2^n)	Squares	Brute-force subset generation, naive recursive Fibonacci

The jump from O(n) to O(n^2) is the one that bites people in practice most often: a nested loop that felt fine on a 50-row test table becomes unusable on a 50,000-row production table, because the work didn't grow 1,000x with the data — it grew 1,000,000x.

Why O(log n) is so much better than it sounds

log n grows unbelievably slowly. For a sorted array of one billion elements, log2(1,000,000,000) is about 30 — binary search finds any element in roughly 30 comparisons, not a billion. Every time you double the input, you only add one more step to an O(log n) algorithm. This is the entire reason database indexes (B-trees) and binary search are worth the trouble: the cost barely grows even as the data grows enormously.

Reading it off actual code

def contains_duplicate_slow(nums):        # O(n^2)
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return True
    return False
 
def contains_duplicate_fast(nums):         # O(n)
    seen = set()
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False

The slow version has a loop nested inside a loop over the same input — that's the visual signature of O(n^2). The fast version does one pass, using a hash set to turn "have I seen this before" from an O(n) scan into an O(1) average-case lookup, at the cost of O(n) extra memory to store seen. This trade — spending memory to save time — shows up constantly, and it's the exact pattern behind the hash-map technique covered in the next lesson.

The honest caveat

Big-O describes the worst case (or, when specified, the average case) as input size grows without bound — it says nothing about which algorithm is faster for a specific, small, real input, and it ignores constant factors entirely. An O(n) algorithm with heavy per-element work can lose to an O(n log n) algorithm with a tiny constant factor, for realistic values of n. Big-O tells you how something scales, not which one to pick in every situation — but "does this scale" is usually the more important question for code that has to survive real growth.