Common Complexity Classes — The Landscape of Efficiency

While infinitely many growth functions exist, a handful of complexity classes dominate algorithm analysis. These classes form the vocabulary of efficiency discussions—when engineers debate approaches, they speak in terms of O(n) versus O(n log n), not 3.7n + 42 versus 2.1n log n + 17.

Mastering these classes means developing intuition for:

• What each complexity feels like at different scales
• What algorithmic patterns produce each complexity
• When a complexity is 'acceptable' versus 'problematic'
• How to recognize each from code structure

This page provides that intuition through exhaustive exploration of each major complexity class, from the lightning-fast O(1) to the effectively-impossible O(n!).

Definition:

An algorithm is O(1) if its runtime doesn't depend on input size. Whether the input has 10 elements or 10 billion, the operation takes (roughly) the same time.

The intuition:

O(1) operations go directly to what they need—no searching, no iteration, no recursion through input. They use structural properties (like indices or hashes) to access data in a fixed number of steps.

What O(1) does NOT mean:

• It doesn't mean exactly 1 operation. O(1) means bounded by a constant—could be 5 operations, 100 operations, or 10,000 operations, as long as it doesn't grow with n.
• It doesn't mean 'fast.' A O(1) operation taking 1 second is slower than an O(n) operation taking 0.001n seconds for n < 1000.

How to recognize O(1) in code:

# O(1) - Direct access
value = array[index]

# O(1) - Fixed operations
def swap(a, b):
    return b, a

# O(1) - Hash table (average case)
def lookup(hashmap, key):
    return hashmap[key]

# NOT O(1) - This is O(n)
def find_max(array):
    return max(array)  # Must examine all elements

Scaling behavior:

O(1) is the gold standard—if you can achieve it, do so.

Definition:

An algorithm is O(log n) if it reduces the problem size by a constant factor at each step. Each step eliminates a fraction of remaining possibilities.

The intuition:

Logarithmic algorithms don't examine every element—they repeatedly 'cut in half' (or thirds, or tenths). Binary search is the canonical example: with each comparison, half the remaining elements are eliminated.

The magic of logarithms:

log₂(n) grows incredibly slowly:

• log₂(1,000) ≈ 10
• log₂(1,000,000) ≈ 20
• log₂(1,000,000,000) ≈ 30

To search 1 billion sorted elements with binary search takes only ~30 comparisons!

What produces O(log n):

• Divide and conquer with one branch: Binary search divides but only follows one half
• Balanced tree traversal: BST search follows one path down
• Halving loops: while n > 0: n = n // 2
• Exponentiation by squaring: Computing x^n in O(log n) multiplications

Canonical examples:

# Binary search - O(log n)
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Halving loop - O(log n)
def count_halves(n):
    count = 0
    while n > 0:
        n = n // 2
        count += 1
    return count  # Returns floor(log₂(n)) + 1

Definition:

An algorithm is O(n) if it performs a constant amount of work for each input element. Double the input, double the work.

The intuition:

Linear algorithms must examine every element at least once—they 'touch' each piece of input but don't repeatedly revisit elements. A single pass through data is the hallmark of linear algorithms.

Scaling behavior:

How to recognize O(n) in code:

# Single loop over input - O(n)
for element in array:
    process(element)  # O(1) per element

# Two sequential loops - still O(n)
for element in array:
    do_something(element)
for element in array:
    do_something_else(element)
# O(n) + O(n) = O(2n) = O(n)

# Sum calculation - O(n)
def sum_array(arr):
    total = 0
    for x in arr:
        total += x
    return total

O(n) is often optimal:

For many problems, O(n) is the best possible:

• Finding an arbitrary element in an unsorted array: Must check each element. Ω(n) lower bound.
• Computing sum: Must read every element. Ω(n) lower bound.
• Determining if any duplicates exist: Without structure, must examine all. Ω(n) lower bound.

When a problem requires examining all input, O(n) is the achievable optimum.

Definition:

An algorithm is O(n log n) if it processes n elements, and for each element (or each level of recursion), it does O(log n) work—or equivalently, it has O(log n) levels of recursion/iteration, each doing O(n) work.

The intuition:

O(n log n) is slightly worse than linear but dramatically better than quadratic. It's the complexity of 'smart' sorting and divide-and-conquer algorithms that split the problem but must still examine all elements.

Why n log n appears:

• Divide and conquer with full processing: Merge sort divides the array (log n levels) and merges all elements at each level (n work per level).
• Repeated halving with linear scans: Some algorithms scan through data while concurrently halving something.

Canonical examples:

# Merge sort - O(n log n)
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])   # T(n/2)
    right = merge_sort(arr[mid:])  # T(n/2)
    return merge(left, right)       # O(n)
# Recurrence: T(n) = 2T(n/2) + O(n) = O(n log n)

# Heap sort - O(n log n)
def heap_sort(arr):
    build_heap(arr)       # O(n)
    for i in range(n):
        extract_max(arr)  # O(log n) each, n times
# Total: O(n) + O(n log n) = O(n log n)

The sorting barrier:

O(n log n) is the lower bound for comparison-based sorting. No comparison sort can do better than Θ(n log n) in the average case. This is why merge sort, heap sort, and quicksort (average case) all hit this bound—they're optimal.

Definition:

An algorithm is O(n²) if it examines every pair of elements, or performs O(n) work for each of n elements.

The intuition:

Quadratic algorithms compare or combine elements pairwise. When you see nested loops where both iterate over input size, expect O(n²).

Scaling behavior (the problem):

This is why O(n²) becomes problematic at scale. What's fine for 100 elements becomes impossibly slow at 100,000.

What produces O(n²):

# Nested loops over same input - O(n²)
for i in range(n):
    for j in range(n):
        process(i, j)

# Bubble sort - O(n²)
for i in range(n):
    for j in range(n - 1 - i):
        if arr[j] > arr[j+1]:
            arr[j], arr[j+1] = arr[j+1], arr[j]

# Checking all pairs - O(n²)
for i in range(n):
    for j in range(i + 1, n):
        if has_property(arr[i], arr[j]):
            count += 1

Definition:

O(n³) algorithms perform cubic work—typically examining all triples of elements or having three nested loops.

The intuition:

Each additional exponent makes scaling dramatically worse. O(n³) processes triples, like checking for three-element relationships.

Scaling reality:

O(n³) is feasible for n up to a few thousand. Beyond that, it becomes impractical quickly.

What produces O(n³):

# Three nested loops - O(n³)
for i in range(n):
    for j in range(n):
        for k in range(n):
            process(i, j, k)

# Matrix multiplication (naive) - O(n³)
for i in range(n):
    for j in range(n):
        for k in range(n):
            C[i][j] += A[i][k] * B[k][j]

# Floyd-Warshall all-pairs shortest path - O(n³)
for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], 
                           dist[i][k] + dist[k][j])

Polynomial time in general:

Algorithms that are O(nᵏ) for any fixed constant k are called 'polynomial-time.' This includes O(n), O(n²), O(n³), etc. Polynomial-time algorithms are generally considered 'tractable' because they scale predictably (if uncomfortably for high exponents).

Definition:

An algorithm is O(2ⁿ) if its runtime doubles with each unit increase in input size. Adding one element doubles the work.

The intuition:

Exponential algorithms explore all possible subsets or combinations. With n elements, there are 2ⁿ possible subsets—exponential algorithms consider them all.

The scaling disaster:

This is why exponential algorithms are called 'intractable.' They work for tiny inputs but become impossible beyond n ≈ 20-40.

What produces O(2ⁿ):

# Generate all subsets - O(2ⁿ)
def all_subsets(arr):
    if not arr:
        return [[]]
    first = arr[0]
    rest_subsets = all_subsets(arr[1:])
    return rest_subsets + [[first] + s for s in rest_subsets]

# Naive Fibonacci - O(2ⁿ) due to overlapping calls
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)
    # Forms a binary tree of calls

# Brute force knapsack - O(2ⁿ)
def knapsack_brute(weights, values, capacity):
    # Try all 2ⁿ subsets of items
    return max(value for subset in all_subsets(range(n))
               if sum(weights[i] for i in subset) <= capacity
               for value in [sum(values[i] for i in subset)])

The exponential signature:

Exponential recursion often has this pattern:

f(n) calls f(n-1) twice: T(n) = 2T(n-1) = O(2ⁿ)