The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Complexity Analysis

Next ►
►

In the previous lesson we learned to express costs with asymptotic notation; in this one we will learn to calculate them. Complexity analysis is the skill of looking at an algorithm — or straight at its code — and determining, without running it, how its time and memory will grow with the input size. It is a first-rate engineering skill: it lets you rule out unworkable designs before writing a single line and pinpoint bottlenecks just by reading code.

We continue with Rutalia. Its team has inherited a backend with functions that are "suddenly" slow now that there are a million orders: looking up an order by identifier, detecting duplicate orders, recording deliveries in a list that never stops growing. In this lesson we will analyze those functions one by one and put numbers behind the intuition.

Contents

  1. Time and space complexity: what exactly we measure
  2. Operation counting and basic rules
  3. Loops: simple, nested, and dependent
  4. Best case, worst case, and average case
  5. Amortized analysis: the dynamic array
  6. Recurrences and the master theorem (introduction)

  1. Time and space complexity: what exactly we measure

Given an algorithm and an input of size n, we define:

  • Time complexity T(n): the number of elementary operations (in the RAM model from lesson 01-01) the algorithm executes.
  • Space complexity S(n): the amount of additional memory it needs, not counting the input. Also called auxiliary space.
Concept What it counts Rutalia example
Time operations executed comparisons when searching for an order
Space (auxiliary) extra memory allocated a set of the IDs already seen
Space (total) input + auxiliary the list of orders + the set

A subtlety that often goes unnoticed: auxiliary space also includes the call stack of recursive functions (every pending call occupies memory). We will look at this in detail in lesson 01-03.

Time and space are often traded against each other: spending more memory (for example, an auxiliary index) can drastically reduce time. A large part of algorithm engineering consists of choosing that trade-off well.

  1. Operation counting and basic rules

The fundamental method is direct: for each line, determine (a) how much it costs to execute once and (b) how many times it executes. The total cost is the sum of all the products. Then simplify with asymptotic notation.

Let's analyze the linear search for an order at Rutalia:

def find_order(orders, target_id):
    """Return the order with that id, or None if it does not exist."""
    for order in orders:            # runs up to n times
        if order["id"] == target_id:  # 1 comparison per iteration
            return order            # at most once
    return None                     # at most once

Worst-case count (the order is not there): the loop runs n times at a constant cost c per iteration, plus a final constant cost. T(n) = c·n + c' = Θ(n). Auxiliary space: just the loop variable → S(n) = Θ(1).

Composition rules we will use constantly:

  • Sequence: consecutive blocks are added. Θ(n) + Θ(n²) = Θ(n²) (the larger one dominates).
  • Loop: the cost of the body multiplied by the number of iterations.
  • Conditional: in the worst case, the cost of the more expensive branch (plus the condition).
  • Function call: the cost of the called function (it does not cost 1 just because it is one line!).

And the reminder from the previous lesson: in Python, x in some_list is Θ(n), some_list.insert(0, x) is Θ(n), sorted(some_list) is Θ(n log n), and a slice some_list[a:b] is Θ(b−a). Counting "lines" instead of actual operations is the classic source of wrong analyses.

  1. Loops: simple, nested, and dependent

3.1 Simple loops

A loop that runs n times with a constant-cost body is Θ(n). If the body costs f(n), the total is n · f(n).

3.2 Independent nested loops

Costs multiply. Here is the naive version of Rutalia's duplicate-order detector (two customers ordering the same item to the same address):

def find_duplicates_v1(orders):
    """Return index pairs of identical orders. Naive version."""
    duplicates = []
    n = len(orders)
    for i in range(n):                      # n iterations
        for j in range(i + 1, n):           # n-1, n-2, ..., 1, 0 iterations
            if (orders[i]["address"] == orders[j]["address"]
                    and orders[i]["item"] == orders[j]["item"]):
                duplicates.append((i, j))
    return duplicates

The inner loop does not always run n times: it runs n−1 times the first time, n−2 the second… It is a dependent loop (it depends on i). The total number of iterations is:

(n−1) + (n−2) + ... + 1 + 0 = n(n−1)/2 = Θ(n²)

This arithmetic sum shows up constantly; the result is worth memorizing: a triangular double loop is quadratic, just like the full n·n double loop (half the work does not change the order). With a million orders: ~5·10¹¹ comparisons. This is, quite literally, the process that was taking hours at Rutalia.

The alternative that uses auxiliary memory:

def find_duplicates_v2(orders):
    """Version with an auxiliary map: Θ(n) time, Θ(n) space."""
    seen = {}            # key -> first index where it appeared
    duplicates = []
    for i, order in enumerate(orders):                # n iterations
        key = (order["address"], order["item"])
        if key in seen:                               # O(1) in a dict (average)
            duplicates.append((seen[key], i))
        else:
            seen[key] = i                             # O(1) (average)
    return duplicates

Θ(n) time in exchange for Θ(n) auxiliary space: a textbook time/space trade-off. (Why the dict achieves O(1) per operation is covered in lesson 01-04.)

3.3 Loops with a multiplicative step

When the control variable is multiplied or divided on every iteration, the number of iterations is logarithmic:

def zoom_levels(n_packages):
    """How many times can we split the delivery area in half?"""
    levels = 0
    while n_packages > 1:
        n_packages //= 2     # divided by 2 on each iteration
        levels += 1
    return levels            # ≈ log2(n) iterations → Θ(log n)

Summary of patterns:

Loop pattern Iterations Order
for i in range(n) n Θ(n)
full n × n double loop n² Θ(n²)
triangular double loop (j from i+1) n(n−1)/2 Θ(n²)
while dividing by 2 log₂ n Θ(log n)
Θ(n) loop with a Θ(log n) body n·log n Θ(n log n)

  1. Best case, worst case, and average case

For the same n, different inputs can cost different amounts. We define three functions:

  • Worst case T_worst(n): the maximum cost over all inputs of size n. It is the default metric: it gives a guarantee.
  • Best case T_best(n): the minimum cost. It is almost never useful on its own (any algorithm with an early exit has a good best case).
  • Average case T_avg(n): the expected cost under some distribution of inputs. It is the most realistic and the hardest: it requires assuming a distribution.

For find_order (linear search), assuming the target order is present and equally likely to be at any position:

Case Situation Cost
Best the order is the first one Θ(1)
Worst it is the last one, or absent Θ(n)
Average uniformly random position (1+2+...+n)/n = (n+1)/2 → Θ(n)

Note: the average case is still linear; "on average I look at half the list" does not change the growth rate. And remember the warning from 01-01: best/worst/average are different functions, and O, Ω, or Θ can be applied to each of them. "The worst case of linear search is Θ(n)" is a complete and correct statement.

At Rutalia this has an operational reading: for the internal dashboard a good average case may be enough; for the route computation that must finish before the vans leave at 8:00, what matters is the worst-case guarantee.

  1. Amortized analysis: the dynamic array

Some structures have operations that are almost always cheap but occasionally expensive. Judging them by their one-off worst case is misleading; the honest thing to do is spread the cost out: that is amortized analysis. The amortized cost of an operation is the total cost of a sequence of m operations divided by m.

The canonical example is the dynamic array — exactly what Python's list.append does. Rutalia records every delivery of the day in a list:

deliveries = []
def record_delivery(delivery):
    deliveries.append(delivery)   # how much does this cost?

Internally, the list allocates an array with a certain capacity. While there is room left, append writes to the next slot: cost 1. When the array fills up, another one is allocated (typically twice the size), the k existing elements are copied over, and then the write happens: cost k+1.

How much do n appends starting from empty cost, with capacity doubling? The copies happen when filling capacities 1, 2, 4, 8, …, and copy that many elements:

total cost ≤ n (writes) + (1 + 2 + 4 + ... + n) (copies) ≤ n + 2n = 3n

Therefore the amortized cost per append is 3n / n = 3 = Θ(1), even though a particular append can cost Θ(n). This is the aggregate technique; finer ones exist (the banker's method, the potential method) that we will not need in this course.

graph LR
    subgraph "Cost per append (n = 1..8)"
    A["1"] --> B["2 (copies 1)"] --> C["3 (copies 2)"] --> D["1"] --> E["5 (copies 4)"] --> F["1"] --> G["1"] --> H["1"]
    end

Two practical consequences for Rutalia:

  • Recording the day's million deliveries with append costs Θ(n) in total: perfect.
  • Beware of the "cousin" operation: deliveries.insert(0, x) (inserting at the front) shifts every element and costs Θ(n) every time, not amortized. A million insertions at the front is Θ(n²). If you need to insert at both ends, the right structure is a different one (collections.deque, which will appear in lesson 01-04).

  1. Recurrences and the master theorem (introduction)

When an algorithm solves a problem by calling itself on smaller inputs, its cost is expressed as a recurrence: an equation where T(n) depends on T at smaller sizes. Here we only need just enough to analyze divide and conquer algorithms; designing recursive algorithms as a technique is the subject of lesson 01-03.

Example: Rutalia keeps its delivery addresses sorted alphabetically and searches with the classic "open in the middle" approach (binary search itself is studied in depth in 04-01; here we only care about its cost). Each step discards half of the addresses with constant work:

T(n) = T(n/2) + c

Unrolling: T(n) = T(n/4) + 2c = T(n/8) + 3c = ... = T(1) + c·log₂ n = Θ(log n).

For divide-and-conquer recurrences there is a general recipe, the master theorem. For recurrences of the form:

T(n) = a · T(n/b) + f(n) with a ≥ 1 subproblems of size n/b and a divide/combine cost of f(n)

compare f(n) with n^(log_b a):

Case Condition Result Example
1 f(n) grows less than n^(log_b a) T(n) = Θ(n^(log_b a)) T(n)=2T(n/2)+1 → Θ(n)
2 f(n) = Θ(n^(log_b a)) T(n) = Θ(n^(log_b a) · log n) T(n)=2T(n/2)+n → Θ(n log n)
3 f(n) grows more (subject to a technical regularity condition) T(n) = Θ(f(n)) T(n)=2T(n/2)+n² → Θ(n²)

Quick checks:

  • Binary search: a=1, b=2 → n^(log₂ 1) = n⁰ = 1; f(n)=Θ(1) matches → case 2 → Θ(log n). ✔
  • Merge sort (which we will see as a scheme in 01-03 and in detail in 04-02): a=2, b=2, f(n)=Θ(n) → n^(log₂ 2) = n matches → case 2 → Θ(n log n). ✔

At an introductory level this is enough: identify a, b, and f(n), compute n^(log_b a), and pick the case. When the recurrence does not fit the pattern (for example T(n) = T(n−1) + n, which gives Θ(n²)), you can always fall back on unrolling the recurrence by hand, as we did with binary search.

Common Mistakes and Tips

  • Counting lines instead of operations. A line with sorted(...), in some_list, or a slice hides Θ(n log n) or Θ(n) costs. Before counting, ask yourself what each expression does on the inside.
  • Multiplying nested loops blindly. If the inner loop depends on the outer one, you have to sum the series. Sometimes the sum comes out smaller than expected: two nested loops where the inner one advances a global pointer (the "two pointers" pattern) can be Θ(n) in total, not Θ(n²).
  • Confusing amortized with average case. Amortized cost is a guarantee over any sequence of operations (no probability involved); the average case depends on an assumed input distribution. append is O(1) amortized always; linear search is Θ(n) on average if the position is uniform.
  • Forgetting about space. An algorithm that is elegant in time can be unworkable in memory (e.g., materializing all pairs of orders: Θ(n²) space with n = 10⁶ is on the order of terabytes). Always analyze both dimensions.
  • Applying the master theorem where it does not apply. It requires subproblems of size n/b (a constant fraction). T(n) = T(n−1) + c is not divide and conquer; it is unrolled by hand (giving Θ(n)).
  • Tip: verify empirically. Measure the time with time.perf_counter() for n, 2n, and 4n: if the time multiplies by ~4 when n doubles, you are looking at something quadratic. Measurement does not replace analysis, but it confirms or refutes it in minutes.

Exercises

Exercise 1: Analyzing three snippets

Determine the time complexity (worst case, in Θ) of each function, justifying the count:

def a(orders):
    total = 0
    for o in orders:
        total += o["weight"]
    for o in orders:
        total -= o["discount"]
    return total

def b(orders):
    result = []
    for o in orders:
        if o["urgent"]:
            result = result + [o]   # watch out for this line!
    return result

def c(zones, orders):   # z zones, n orders
    assignments = []
    for zone in zones:
        for o in orders:
            if o["zip_code"] == zone["zip_code"]:
                assignments.append((zone["id"], o["id"]))
    return assignments

Exercise 2: Best, worst, and average at Rutalia

The following function checks whether a discount code is in the list of valid codes (unsorted, no duplicates, n codes). Assuming that when the code is valid its position is uniformly random, and that 50% of the checks are for invalid codes, work out the best case, worst case, and average case.

def is_valid_code(codes, code):
    for c in codes:
        if c == code:
            return True
    return False

Exercise 3: Recurrences

Solve using the master theorem (or by unrolling, if it does not apply):

  1. T(n) = 4·T(n/2) + n
  2. T(n) = T(n/2) + n
  3. T(n) = T(n−1) + c

Solutions

Solution 1

  • a: two Θ(n) loops in sequence (not nested): Θ(n) + Θ(n) = Θ(n).
  • b: the trap is in result = result + [o], which creates a new list by copying the k accumulated elements: cost Θ(k) on iteration k. In the worst case (all urgent): 1 + 2 + ... + n = Θ(n²). With result.append(o) (amortized O(1)) it would be Θ(n). A single line makes the difference between 0.01 s and hours with a million orders.
  • c: independent nested loops: z iterations × n iterations of constant work = Θ(z·n). With two size variables, the answer must include both; saying "Θ(n²)" would be incorrect unless z ≈ n.

Solution 2

  • Best case: the code is the first one → Θ(1).
  • Worst case: the code is invalid (or the last one) → n comparisons → Θ(n).
  • Average case: with probability 1/2 the code is invalid (n comparisons); with probability 1/2 it is valid and on average (n+1)/2 elements are examined. Average cost = ½·n + ½·(n+1)/2 = 3n/4 + 1/4 → Θ(n). As always with linear search, the average case does not drop below linear order.

Solution 3

  1. a=4, b=2, f(n)=n. n^(log₂ 4) = n², and f(n)=n grows less → case 1 → Θ(n²).
  2. a=1, b=2, f(n)=n. n^(log₂ 1) = 1, and f(n)=n grows more (and satisfies the regularity condition) → case 3 → Θ(n). Intuition: the first level already costs n, and the following ones n/2, n/4… add up to less than 2n.
  3. The master theorem does not apply (the subproblem is n−1, not a fraction of n). Unrolling: c + c + ... + c, n times → Θ(n).

Conclusion

We now know how to calculate costs: count operations line by line, compose sequences (add) and loops (multiply, or sum the series when they are dependent), distinguish best/worst/average case depending on the guarantee we need, spread out occasional expensive costs with amortized analysis (the dynamic array as the star example), and solve divide-and-conquer recurrences with the master theorem. Applied to Rutalia, the diagnosis is clear: the quadratic duplicate detector was the hours-long process, and a time/space trade-off brings it down to seconds.

In the analysis of recurrences a protagonist has appeared that we have not yet given its due: algorithms that call themselves. In the next lesson, Recursion and Dynamic Programming, we will learn to design correct recursions (base case, progress, call stack), to use divide and conquer as a general scheme, and to rescue recursions that repeat work through memoization and dynamic programming — with a Rutalia delivery problem over the city grid as our practical thread.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2026. All rights reserved