Big O Notation

Big O notation expresses an upper bound on how an algorithm's running time or memory use grows as the input size n increases. It ignores constant factors and smaller terms, so it describes the shape of the growth rather than exact timings.

Why it matters

Big O lets you compare algorithms and predict which will still work when the data gets large. An algorithm that is fine for 100 items may be unusable at 10 million. Common classes, from fastest to slowest growth, are O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) typical of efficient sorting, O(n^2) quadratic and O(2^n) exponential. It is a model, not a benchmark: a lower complexity class can lose on small inputs, and cache behavior and constants matter in practice.

Example

def has_duplicate_slow(xs):      # O(n^2): compares every pair
    return any(xs[i] == xs[j] for i in range(len(xs)) for j in range(i))

def has_duplicate_fast(xs):      # O(n): one pass with a set
    return len(set(xs)) != len(xs)

With 100,000 items, the first does billions of comparisons and the second does about one hundred thousand operations.

Common mistakes

• Treating Big O as exact running time.
• Forgetting hidden costs, such as an O(n) call inside a loop making it O(n^2).
• Ignoring space complexity.

Related

• Algorithm
• Recursion
• Hash table
• Benchmark

This page is general information written by our editorial team and updated when documentation changes. Servers and providers differ, so test changes safely first. See our editorial policy and disclaimer.