Big-O and Complexity

How an algorithm's cost grows with input size, ignoring constants. The language for comparing solutions before you run them.

Level: beginner

What is it?

Big-O notation describes how the cost of an algorithm — steps or memory — grows as the input size n grows, dropping constant factors and lower-order terms. O(1) is constant, O(log n) logarithmic, O(n) linear, O(n log n) linearithmic, O(n²) quadratic, O(2ⁿ) exponential. It is an upper bound, usually stated for the worst case; average-case and amortized costs are separate statements.

Why does it matter?

A program that is fine on 100 items can take days on a million. Big-O tells you which part of the design will hurt at scale before you run anything, and it is the shared vocabulary of every interview and design review.

Mental model

A taxi meter and a distance. Ignore the starting fare and the exact route; ask only how the price grows as the trip gets longer. Doubling the input on an O(n) algorithm doubles the cost; on O(n²) it quadruples; on O(log n) it adds one step.

How it works

Count how the number of basic operations grows with n; drop constants (3n is O(n)) and smaller terms (n² + n is O(n²)).
Sequential steps add (O(n) then O(n) is O(n)); nested loops multiply (O(n) inside O(n) is O(n²)).
Halving the problem each step gives O(log n); doing linear work per halving gives O(n log n).
Space complexity counts extra memory beyond the input. Time and space often trade off: a hash set makes lookups O(1) at the cost of O(n) memory.
Amortized cost averages over a sequence: appending to a dynamic array is O(1) amortized even though an occasional resize costs O(n).
Big-O hides constants. For small n, or when memory locality dominates, an O(n²) loop can beat an O(n log n) one.

Steps

Pick the input size n
Count the dominant operation
Nested loops multiply, sequences add
Drop constants and small terms
State the worst case and the space

Code example: The same question at two costs

def has_duplicate_quadratic(xs):        # O(n^2) time, O(1) space
    for i in range(len(xs)):
        for j in range(i + 1, len(xs)):
            if xs[i] == xs[j]:
                return True
    return False

def has_duplicate_linear(xs):           # O(n) time, O(n) space
    seen = set()
    for x in xs:
        if x in seen:
            return True
        seen.add(x)
    return False

Complexity and trade-offs

Time: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)

Space: Count the extra memory the algorithm allocates, not the input

Trade-offs

Spending memory (a set, a cache) to save time is the most common trade
Constants and cache behavior matter at small n; asymptotics win at large n
Worst case, average case, and amortized cost answer different questions

Real-world usage

Choosing between two designs before writing either
Explaining why a query or endpoint slows down as data grows
Interview answers: state the cost of every solution you propose

Common mistakes

Reading O(n) as 'n operations' — it is a growth rate, not an exact count.
Forgetting the hidden loops inside library calls (x in list, string concatenation, list.insert(0, x)).
Optimizing an O(n) loop while an O(n²) one sits beside it.

Interview questions

What is the time complexity of a nested loop over the same array?

Typically O(n²): the inner loop runs about n times for each of the n outer iterations. If the inner range shrinks (j from i+1), it is still n²/2 comparisons, which is O(n²).

What does amortized O(1) mean?

Averaged over a sequence of operations, each costs constant time, even if a few are expensive. Appending to a dynamic array occasionally copies everything, but resizes double the capacity, so the total cost of n appends is O(n).

Can an O(n²) algorithm be faster than an O(n log n) one?

Yes for small n or when the constants and memory access patterns favor it; that is why real sorts switch to insertion sort on tiny ranges. Asymptotic order only wins as n grows.

Class	Operations at n = 1,000	Typical source
O(1)	1	Array index, hash lookup
O(log n)	≈ 10	Binary search, balanced tree
O(n)	1,000	Linear scan
O(n log n)	≈ 10,000	Merge sort, heap sort
O(n²)	1,000,000	Nested loops, bubble sort
O(2ⁿ)	≈ 10³⁰¹	Trying every subset