Big-O Notation & Algorithmic Complexity

Learn to measure and reason about how an algorithm's running time and memory usage grow as input size increases

Introduction

Before we can pick the right data structure or algorithm for a problem, we need a common language for describing how "fast" or "efficient" a solution actually is, independent of the specific computer it runs on. That language is Big-O notation. It lets us compare two approaches to the same problem and predict how each one will behave as the input grows from ten items to ten million. Every data structure and algorithm in this course will be evaluated in terms of Big-O, so mastering it here pays off in every lesson that follows.

What is Big-O Notation?

Big-O notation describes the upper bound on how the runtime (or memory usage) of an algorithm grows as the size of its input, usually called n, increases. It deliberately ignores hardware speed, programming language, and constant-time overhead, focusing only on the shape of the growth curve.

Why "Asymptotic" Analysis?

We care about large inputs, since that's where inefficiency hurts most
It lets us compare algorithms without running them on identical hardware
It exposes bottlenecks early, before they become expensive production incidents
It's the shared vocabulary used in technical interviews and engineering design docs

Common Time Complexities

A handful of complexity classes cover the vast majority of algorithms you'll encounter. Here they are, ordered from fastest to slowest growth. The chart below plots all of them at once, the flat lines near the bottom are the ones you want, and the near-vertical ones are the ones that will sink you at scale:

Figure 1: The seven complexity classes over inputs 1 to 10. O(1) and O(log n) stay nearly flat, while O(n²), O(2ⁿ), and O(n!) climb so fast they leave the top of the plot (O(n!) first, near n = 5). This gap is the whole reason Big-O matters.

O(1) - Constant TimeFastest

The runtime doesn't depend on the size of the input at all. Array indexing and (average-case) dictionary lookups are the classic examples.

def get_first_element(items: list[int]) -> int:
    # Always exactly one operation, no matter how large "items" is
    return items[0]

def lookup_price(prices: dict[str, float], sku: str) -> float:
    # Dict lookups are O(1) on average, thanks to hashing
    return prices[sku]

O(log n) - Logarithmic Time

The runtime grows very slowly because each step eliminates a large fraction of the remaining work, most commonly by repeatedly halving the problem.

def binary_search(sorted_items: list[int], target: int) -> int:
    low, high = 0, len(sorted_items) - 1

    while low <= high:
        mid = (low + high) // 2
        if sorted_items[mid] == target:
            return mid
        elif sorted_items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

# Each comparison eliminates half the remaining search space

O(n) - Linear Time

The runtime grows directly in proportion to the input size. Any algorithm that must look at every element at least once falls into this category.

def find_max(items: list[int]) -> int:
    largest = items[0]
    for item in items:
        # We touch every element exactly once
        if item > largest:
            largest = item
    return largest

O(n log n) - Linearithmic Time

Common in efficient sorting algorithms: the input is split logarithmically, but linear work is done at each level of the split. We'll build merge sort from scratch in Lesson 14.

def sort_scores(scores: list[int]) -> list[int]:
    # Python's built-in sort (Timsort) runs in O(n log n)
    return sorted(scores)

def merge_sort(items: list[int]) -> list[int]:
    if len(items) <= 1:
        return items

    mid = len(items) // 2
    left = merge_sort(items[:mid])       # log n levels of splitting
    right = merge_sort(items[mid:])
    return merge(left, right)            # n work to merge at each level

def merge(left: list[int], right: list[int]) -> list[int]:
    result: list[int] = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

O(n²) - Quadratic TimeWatch out

Nested loops over the same input are the usual culprit. Fine for small inputs, painful once n reaches the thousands.

def has_duplicate_pairs(items: list[int]) -> bool:
    # Nested loop: every element compared against every other element
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

def bubble_sort(items: list[int]) -> list[int]:
    n = len(items)
    for i in range(n):
        for j in range(n - i - 1):
            if items[j] > items[j + 1]:
                items[j], items[j + 1] = items[j + 1], items[j]
    return items

O(2ⁿ) - Exponential TimeDangerous

Runtime doubles with every additional input element. Naive recursive solutions without memoization frequently end up here, this is exactly the trap Dynamic Programming solves.

def fibonacci(n: int) -> int:
    # Naive recursion: each call spawns two more calls
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

# fibonacci(30) makes over 2.6 million calls

O(n!) - Factorial TimeAvoid at scale

Generating every possible ordering of the input. Only practical for very small n.

from itertools import permutations

def all_orderings(items: list[int]) -> list[tuple[int, ...]]:
    # Every possible ordering of "items" - n! of them
    return list(permutations(items))

# all_orderings of 10 items produces 3,628,800 results

Complexity	Name	Operations at n = 10	Operations at n = 1,000
`O(1)`	Constant	1	1
`O(log n)`	Logarithmic	~3	~10
`O(n)`	Linear	10	1,000
`O(n log n)`	Linearithmic	~33	~10,000
`O(n²)`	Quadratic	100	1,000,000
`O(2ⁿ)`	Exponential	1,024	astronomically large

The Takeaway

At n = 10, almost every algorithm feels fast. The differences only become visible, and matter, once your data grows. Big-O is how you predict that pain before it happens in production.

Rules for Calculating Big-O

You rarely need to derive Big-O from a formal proof. These three rules cover almost every situation you'll run into.

1. Drop Constant Factors

Doing something twice as many times still grows at the same rate, so constants are dropped.

def process_twice(items: list[int]) -> None:
    for item in items:      # O(n)
        print(item)
    for item in items:      # O(n)
        print(item)

# Total work: O(n) + O(n) = O(2n) -> simplifies to O(n)
# Constants are dropped because they don't change the growth shape

2. Keep Only the Dominant Term

When an algorithm does multiple things in sequence, only the slowest-growing part matters for large inputs.

def mixed_work(items: list[int]) -> None:
    for item in items:                      # O(n)
        print(item)

    for i in range(len(items)):             # O(n^2)
        for j in range(len(items)):
            print(items[i], items[j])

# Total work: O(n) + O(n^2) -> simplifies to O(n^2)
# The slowest-growing term is dropped; the dominant term wins

3. Different Inputs Get Different Variables

Don't collapse two unrelated inputs into a single n, that hides real information about how your algorithm scales.

def print_all_pairs(list_a: list[int], list_b: list[int]) -> None:
    for a in list_a:          # size m
        for b in list_b:
            print(a, b)

# This is O(m * n), NOT O(n^2) - two different inputs
# get two different variables in the notation

Space Complexity

Big-O isn't just about time. Space complexity measures the extra memory an algorithm needs, beyond the input itself, as that input grows. Many algorithms trade time for space, or vice versa, and understanding both sides lets you make that trade-off deliberately.

def duplicate_list(items: list[int]) -> list[int]:
    # Creates a brand new list the same size as the input
    return [item for item in items]        # O(n) extra space

def sum_in_place(items: list[int]) -> int:
    total = 0
    for item in items:
        total += item                       # O(1) extra space
    return total

Note: The input itself is not counted toward space complexity, only the additional memory the algorithm allocates while running.

Best, Average, and Worst Case

The same algorithm can behave differently depending on the input it receives. We describe this with three scenarios:

Best Case (Ω)The minimum time needed, e.g. linear search finding the target on the first try

Average Case (Θ)The expected time across typical, randomly distributed inputs

Worst Case (O)The maximum time needed, e.g. linear search when the target is last or missing

In practice, engineers talk about Big-O almost exclusively because it's the worst-case guarantee, and worst cases are what break systems in production. Throughout this course, unless stated otherwise, every complexity we quote refers to the worst case.

Key Takeaways

Big-O describes growth, not raw speed - it tells you how runtime scales as input size increases
Constants and non-dominant terms are dropped - only the fastest-growing part of the expression matters at scale
O(1) and O(log n) scale beautifully, while O(2ⁿ) and O(n!) become unusable almost immediately
Space complexity matters too - track the extra memory your algorithm allocates, not just its runtime
Worst-case analysis is the default in engineering, because that's the guarantee your system needs to survive

Back to "Index"

Data Structures & AlgorithmsLesson 1

Next: "Arrays & Dynamic Arrays"