Big O Notation: Measuring Efficiency

Big O notation describes how an algorithm’s running time (or memory use) grows as the input size grows — not the exact number of seconds, which depends on the specific computer, but the underlying pattern of growth.

Common complexities, from best to worst

O(1)        constant     -- looking up a value by key in a dictionarynO(log n)    logarithmic  -- binary search in a sorted listnO(n)        linear       -- checking every item in a list oncenO(n log n)  linearithmic -- efficient sorting algorithms (merge sort, quicksort)nO(n²)       quadratic    -- comparing every item to every other item (nested loops)

n represents the size of the input. An O(n) algorithm run on a list twice as long takes roughly twice as long; an O(n²) algorithm run on a list twice as long takes roughly four times as long — the gap between these grows dramatically as n grows.

A concrete example

def has_duplicate_slow(items):        # O(n²) -- nested loop compares every pairn    for i in range(len(items)):n        for j in range(len(items)):n            if i != j and items[i] == items[j]:n                return Truen    return Falsenndef has_duplicate_fast(items):        # O(n) -- one pass, using a set for O(1) lookupsn    seen = set()n    for item in items:n        if item in seen:n            return Truen        seen.add(item)n    return False

Both functions answer the exact same question correctly. On a list of 100,000 items, the difference between these two is the difference between a program that responds instantly and one that visibly hangs.

Space complexity

Big O also describes memory use, not just time — has_duplicate_fast above trades a small amount of extra memory (the seen set) for a large improvement in speed, a trade-off that shows up constantly throughout this entire course.