Big O Notation Explained with Examples

Two programs that solve the same problem may both finish instantly on 100 items, yet one takes seconds and the other hours on 10 million. Big O notation explains why. It is the standard language for discussing algorithm efficiency in textbooks, documentation and technical interviews.

What Big O notation measures

Big O counts how the number of basic steps (comparisons, assignments, arithmetic operations) grows with the input size n, for large n. Formally, a function f(n) is O(g(n)) if there are positive constants c and n₀ such that:

$$f(n) \le c \cdot g(n) \quad \text{for all } n \ge n_0$$

In words, beyond some input size, f grows no faster than a constant multiple of g. That is why constants and lower order terms disappear: 3n² + 5n + 20 is O(n²), because for large n the n² term dominates.

Related notations are Big Omega (Ω, a lower bound) and Big Theta (Θ, a tight bound). Analyses also distinguish the worst case, average case and best case. Big O of the worst case is the most commonly quoted figure because it gives a guarantee.

Common complexity classes

Download diagram (WebP)

How to find the Big O of code

1. Count loops. A single loop over n items is O(n). Two nested loops over n are O(n²). A loop that halves the problem each step is O(log n).
2. Add sequential parts, then keep the largest. O(n) + O(n²) = O(n²).
3. Multiply nested parts. An O(log n) operation inside an O(n) loop gives O(n log n).
4. Drop constants. O(2n) is O(n); O(n/2) is O(n).
5. Use different letters for different inputs. Looping over a list of length a and another of length b nested gives O(a × b), not O(n²).
6. Recursion: set up a recurrence. Merge sort satisfies T(n) = 2T(n/2) + O(n), which solves to O(n log n).

def has_duplicate_pairwise(items):      # O(n^2): compares every pair
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

def has_duplicate_set(items):           # O(n) on average: one pass with a hash set
    seen = set()
    for x in items:
        if x in seen:
            return True
        seen.add(x)
    return False

Big O of common data structure operations

Knowing these costs lets you choose a structure by looking at which operations your program performs most often.

Space complexity

Big O also describes memory. The set based duplicate check above uses O(n) extra space; the pairwise check uses O(1) extra space. Many design decisions trade time for space, for example caching results (memoisation) or building an index. The memory overhead of arrays vs linked lists is a practical example.

Amortised complexity

Some operations are usually cheap but occasionally expensive. Appending to a dynamic array is O(1) most of the time, but O(n) when the array must grow and copy. Because growth doubles the capacity, the total cost of n appends is O(n), so each append is amortised O(1).

Common mistakes

• Treating Big O as exact running time; it hides constants that matter for small n.
• Forgetting hidden loops inside library calls, such as searching a list with the in operator inside another loop.
• Ignoring the cost of data movement and memory access patterns.
• Quoting the average case when inputs may be adversarial; quicksort is O(n²) in the worst case.

Big O thinking applies across computer science: from choosing data structures to designing database queries, where good normalization and indexes avoid scanning whole tables. Language implementation affects only constant factors, as explained in compiled vs interpreted languages, while the choice of algorithm changes the growth rate itself. Writing unit tests for edge cases helps confirm that a faster algorithm still gives correct results.