Complexity Analysis

Big O Notation

Big O notation is a mathematical way to describe the limiting behavior of a function as its argument grows. In computer science we use it to describe how an algorithm's time or space requirements scale with input size, ignoring constant factors and lower-order terms.

Big O notation provides an upper bound on the growth rate of an algorithm's resource requirements. It helps us understand how an algorithm's performance scales with input size, allowing us to compare different algorithms and make informed decisions about which one to use.

Common Big O Complexities

Notation Name Example
O(1) Constant Array access; hash table lookup (average case — worst case is O(n) when every key collides)
O(log n) Logarithmic Binary search
O(n) Linear Linear search, iterating through array
O(n log n) Linearithmic Merge sort, heap sort
O(n²) Quadratic Bubble sort, nested loops
O(2ⁿ) Exponential Recursive Fibonacci (naive)
O(n!) Factorial Generating all permutations

Time Complexity

Time complexity describes how the runtime of an algorithm increases as the input size grows. It's one of the most important metrics for evaluating algorithm efficiency.

Analyzing Time Complexity

To analyze time complexity, count the number of basic operations performed: 


# Example: Linear Search
def linear_search(arr, target):
    for i in range(len(arr)):      # O(n) iterations
        if arr[i] == target:        # O(1) operation
            return i                # O(1) operation
    return -1                       # O(1) operation

# Overall: O(n) time complexity

Asymptotic Notation and Case Analysis Are Two Different Things

This is the most commonly confused point in complexity analysis, and it is worth getting straight before anything else. You will often see O described as "worst case", Ω as "best case" and Θ as "average case". That is not what they mean. They are independent ideas that combine freely.

Asymptotic notation bounds a function

Given some function f(n) — whatever function you have chosen to study — the notation describes how it grows:

  • O(g(n)) — upper bound. f grows no faster than g. Formally: there exist constants c > 0 and n0 such that f(n) ≤ c·g(n) for all n ≥ n0.
  • Ω(g(n)) — lower bound. f grows at least as fast as g.
  • Θ(g(n)) — tight bound. Both at once: f is O(g) and Ω(g).
  • o(g(n)) and ω(g(n)): strict versions — f grows strictly slower, or strictly faster.

Case analysis chooses which function you bound

  • Best case: the input of size n that the algorithm handles fastest.
  • Average case: the expectation over some stated input distribution. "Average" is meaningless without saying which distribution.
  • Worst case: the input of size n that the algorithm handles slowest. This is usually what you want, because it is the only guarantee.

The two axes combine

Every one of these statements about insertion sort is well-formed and true: 

Best case  is Θ(n)      - already-sorted input, one comparison per element
Worst case is Θ(n²)     - reverse-sorted input
Worst case is O(n³)       - true, just a loose upper bound
Best case  is O(n²)       - also true, also loose
Worst case is Ω(n²)     - the quadratic behaviour is unavoidable on that input

Notice that "best case is O(n²)" is perfectly valid. O is an upper bound, and an upper bound does not have to be tight. If O really meant "worst case", that sentence would be self-contradictory.

In everyday use people write O when they mean Θ, and it is usually harmless. But when a bound matters — when you are proving something, or comparing two algorithms whose bounds are close — say which case you are analysing and which bound you are asserting.

Space Complexity

Space complexity describes how much memory an algorithm uses relative to the input size.

Auxiliary space is the extra memory the algorithm allocates beyond its input; total space includes the input itself. By convention, when someone says "binary search uses O(1) space" they mean auxiliary space — the input array is O(n) but is not counted, because the caller already had it. Every space figure on this site is auxiliary space unless stated otherwise. It is worth being explicit about which you mean, since the two differ by an O(n) term for any algorithm that takes an array.

Space Complexity Examples


# O(1) space - constant space
def find_max(arr):
    max_val = arr[0]           # O(1) space
    for num in arr:            # O(1) space for loop variable
        if num > max_val:
            max_val = num
    return max_val

# O(n) space - linear space
def copy_array(arr):
    result = []                # O(n) space
    for num in arr:
        result.append(num)
    return result

# O(log n) space - recursive call stack
def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

Complexity Comparison

Understanding how different complexities compare helps in choosing the right algorithm:

For an input size of n = 1,000,000:

  • O(1): 1 operation
  • O(log n): ~20 operations
  • O(n): 1,000,000 operations
  • O(n log n): ~20,000,000 operations (n × log₂(n) ≈ 1,000,000 × 20)
  • O(n²): 1,000,000,000,000 operations

As you can see, the difference between O(n) and O(n²) becomes enormous as input size grows!

Practical Tips for Complexity Analysis

  • Focus on the dominant term: O(n² + n) = O(n²)
  • Ignore constants: O(2n) = O(n). Note this makes O(n/2) and O(n) the same set — they are equal, not approximately equal.
  • Consider nested loops: nested loops often indicate O(n²) or higher — but check the bounds. A loop running to n with an inner loop running to log n is O(n log n).
  • Recursion depth matters: each recursive call adds a stack frame, so depth is a space cost.
  • Data structure choice: different operations have different complexities.

Amortized Analysis

Some operations are occasionally expensive but cheap on average across a sequence, and worst-case analysis of a single operation badly misrepresents them. Appending to a dynamic array is the standard example: usually O(1), but when capacity is exhausted the array is reallocated and copied in O(n). Because capacity doubles, those copies happen exponentially rarely, and the total cost of n appends is O(n) — so each append is O(1) amortized.

Amortized is not the same as average-case. Average-case is a probabilistic claim over inputs; amortized is a worst-case guarantee over a sequence of operations, with no randomness involved. Union-Find's O(α(n)) and the O(1) of hash table insertion under doubling are both amortized bounds.

Where Asymptotic Analysis Stops Helping

  • Constants matter at real sizes. An O(n log n) algorithm with a large constant can lose to an O(n²) one for n in the hundreds. This is exactly why practical sorts switch to insertion sort on small subarrays.
  • The RAM model ignores caches. It charges the same for every memory access, but a cache miss can cost two orders of magnitude more than a hit. This is why quicksort routinely beats heapsort despite the worse worst case — it has far better locality.
  • Pseudo-polynomial is not polynomial. An algorithm running in O(n·W) is polynomial in the value W but exponential in the number of bits needed to write W down. See the knapsack discussion in Dynamic Programming.

What's Next?

Now that you understand complexity analysis, you're ready to explore specific algorithms. Check out: