Embercode: AI-powered software engineer course

The brief

You have spent four lessons predicting how code grows. Now you will make the computer check your predictions. The assignment is to build a complexity lab: a Python program that runs several functions on inputs of growing size, counts the steps each one takes, and decides from those counts which growth class each function belongs to.

This is a real technique. Engineers call it an empirical growth test, and they use it when a function is too tangled to analyse by hand or when they want to confirm that a change really did turn a quadratic loop into a linear one. It is also a good way to find out whether your own analysis is right, because the machine does not make arithmetic mistakes.

The assignment has four parts and one stretch. Plan about an hour. Write each part as its own function and test it before moving on. Do not read the hints until you have tried each part for at least ten minutes. The reference solution at the end is for checking your work, not for copying: if you copy it you will learn much less than if you get stuck, think, and then compare.

What you will build

Part A: instrumented functions. An instrumented function is one with a counter inside it that goes up each time it does one unit of work. Write seven functions. Each takes a size n and returns the number of steps it took.

Function	What it does	Step you count	Expected class
`first_item(n)`	reads the first element of a list of n items	one read	O(1)
`binary_search_worst(n)`	binary search for a target larger than every item	one loop pass	O(log n)
`linear_search_worst(n)`	linear search for a value that is missing	one comparison	O(n)
`merge_sort_comparisons(n)`	merge sort of n pseudo-random numbers	one comparison during merging	O(n log n)
`duplicate_pairs(n)`	compares every pair in a list with no duplicates	one pair comparison	O(n^2)
`triple_checks(n)`	visits every triple of positions with `i < j < k`	one triple	O(n^3)
`fib_calls(n)`	naive recursive Fibonacci	one call	exponential

Part B: the classifier. Write classify(sizes, counts). It receives the input sizes you tried and the step counts you measured, and returns a label. The idea is to compare how much the count grew with how much the input grew. If the size multiplied by k and the count multiplied by g, then the growth exponent is log(g) / log(k). For a function that is O(n^2), the exponent is about 2. For O(n) it is about 1. For O(1) it is about 0.

Use these cut-offs on the exponent:

Exponent below	Label
0.05	`O(1)`
0.30	`O(log n)`
0.75	`O(sqrt n)`
1.07	`O(n)`
1.40	`O(n log n)`
2.40	`O(n^2)`
3.40	`O(n^3)`
anything higher	`worse than polynomial`

The cut-offs sit between the ideal exponents, with room for the small terms that Big-O throws away. A merge sort measured between 1,000 and 8,000 items has an exponent near 1.14, because n log n grows slightly faster than n, which is why O(n log n) begins at 1.07. Logarithms have a small positive exponent over a finite range, which is why O(log n) extends up to 0.30.

Part C: the report. Write a function that runs every lab entry and prints one aligned row per function with the function name, the list of counts and the class. Use the sizes in the starter table below.

Part D: written analysis. Answer five short questions about your results, in a comment block or a text file. They are listed at the end.

Stretch: space and amortised cost. Measure the recursion depth of a recursive factorial and a recursive binary search, and classify those depths with the same classify. Then measure the cost per append of a doubling dynamic array and show that it stays near a constant.

Input and output

The program takes no input. It prints a table. Two behaviours you can check by hand while you build it:

classify([1000, 2000, 4000, 8000], [1000, 2000, 4000, 8000])   # counts grew 8x as n grew 8x

O(n)

classify([100, 200, 400], [100, 400, 1600])   # counts grew 16x as n grew 4x

O(n^2)

classify([10, 20, 40], [5, 5, 5])             # counts did not grow

O(1)

The sizes to use for each lab entry are:

Function	Sizes
`first_item`, `binary_search_worst`, `linear_search_worst`, `merge_sort_comparisons`	1000, 2000, 4000, 8000
`duplicate_pairs`	100, 200, 400, 800
`triple_checks`	20, 40, 80, 160
`fib_calls`	10, 12, 14, 16

Why different sizes? Each function has its own speed. A triple loop on 8,000 items would take hundreds of billions of steps. Choosing sizes the machine can finish in a second or two is part of designing a lab.

The report your program should print looks like this. Your counts for merge sort depend on the way you generate the random numbers, so yours may differ slightly, but the class must match.

function                        counts                                    class
first item                      [1, 1, 1, 1]                              O(1)
binary search, missing target   [10, 11, 12, 13]                          O(log n)
linear search, missing target   [1000, 2000, 4000, 8000]                  O(n)
merge sort comparisons          [8715, 19419, 42856, 93640]               O(n log n)
all pairs, no duplicate         [4950, 19900, 79800, 319600]              O(n^2)
all triples                     [1140, 9880, 82160, 669920]               O(n^3)
naive fib calls                 [177, 465, 1219, 3193]                    worse than polynomial

Requirements checklist

Copy this list into your notes and tick items as you go.

Part D: the five questions

Your classify for merge sort uses the exponent from 1,000 to 8,000 items. Explain in two sentences why a pure n log n function has an exponent above 1, and why that does not make it quadratic.
binary_search_worst returned 10, 11, 12, 13 for the four sizes. Explain why each doubling of n adds exactly one step.
fib_calls is labelled worse than polynomial. Estimate its calls for n = 40 from the n = 16 count and a growth factor of about 1.6 per step of n, and say whether you would wait for it.
What is the auxiliary space of merge_sort_comparisons as written, counting the stack? Is the stack or the lists the larger part?
A friend says "the lab proves linear_search_worst is O(n)". Why is that not quite right, and what would a proof need?

Grading rubric

Level	What it looks like
60 percent	Parts A and B work for the first four functions (O(1), O(log n), O(n), O(n log n)). `classify` is written but the cut-offs are rough, so one or two classes are wrong. The report prints but is not aligned. Part D is partly answered.
80 percent	All seven functions work and all classes are correct. `classify` uses the exponent and the specified cut-offs. The report is aligned and runs in under a few seconds. Part D answers all five questions, with correct reasons for at least four. Code is clean: no repeated blocks, clear names.
100 percent	Everything in the 80 percent level, plus the stretch: recursion depth and amortised cost are measured and explained. The report is built from one data table so adding a function means adding one line. Part D answers include the limits of an empirical test (see question 5), such as the size range, small terms and worst-case inputs. You can state, for each function, the analysis you did by hand and show that the lab agrees.

Hints

Open a hint only after you have tried the step yourself.

Hint 1: the counters

Start with linear_search_worst. Make a list items = list(range(n)), loop over it, add one to steps per comparison and return steps. Do not break early: the target is missing, so the loop must run to the end. The other functions follow the same shape: a counter variable, a loop or recursion, and a return of the counter.

Hint 2: binary search with a missing target

Use low = 0, high = n - 1. While low <= high, add one to steps, take the middle, and because the target is larger than every item always move low = mid + 1. The loop ends when low passes high. Check your answer by hand for n = 8: the range shrinks 8, 4, 2, 1, so about 4 passes.

Hint 3: counting inside a recursive function

The counter must survive between calls. Use a list with one element, calls = [0], and an inner function that adds to calls[0]. A plain integer assigned inside the inner function would create a new local variable, and Python would raise UnboundLocalError if you used += on it without nonlocal.

Hint 4: merge sort with a seeded random list

random.Random(n) creates a random number generator seeded with n, so every run with the same n gives the same data. Build the list with rng.randint(0, 10**6). Count one step each time you compare left[i] with right[j] in the merge loop. Sort by recursion on slices; the slices cost extra copying, but we are counting comparisons, not copies.

Hint 5: classify

Compute growth = counts[-1] / counts[0] and scale = sizes[-1] / sizes[0], then exponent = math.log(growth) / math.log(scale). Walk through the cut-off list in order and return the label of the first cut-off the exponent is below. If a count is constant, growth is 1 and math.log(1) is 0, so the exponent is 0 and the label is O(1).

Hint 6: the report

Store the lab as a list of tuples (name, function, sizes). The report is one loop over that list: counts = [fn(n) for n in sizes]. Use f-string widths such as {name:<32} to align the columns.

Hint 7: the stretch

For the recursion depth, pass a depth argument that is 1 at the first call and depth + 1 in each recursive call, and keep the largest value in a one-element list. For the amortised cost, reuse the simulation from lesson four: add 1 for each write, add size when the array is full, double the capacity, and divide the total by n.

Reference solution

Try the whole assignment before opening this. The program below is complete. Run it, compare the output with yours, and read the parts where yours differs.

Solution

Python · editable

import math
import random

def first_item(n):
    items = list(range(n))
    steps = 1
    _ = items[0]
    return steps

def linear_search_worst(n):
    items = list(range(n))
    steps = 0
    for x in items:
        steps += 1
        if x == -1:
            break
    return steps

def binary_search_worst(n):
    items = list(range(n))
    low, high, steps = 0, n - 1, 0
    while low <= high:
        steps += 1
        mid = (low + high) // 2
        if items[mid] < n:
            low = mid + 1
        else:
            high = mid - 1
    return steps

def merge_sort_comparisons(n):
    rng = random.Random(n)
    data = [rng.randint(0, 10**6) for _ in range(n)]
    counter = [0]

def sort(a):
        if len(a) <= 1:
            return a
        mid = len(a) // 2
        left, right = sort(a[:mid]), sort(a[mid:])
        out, i, j = [], 0, 0
        while i < len(left) and j < len(right):
            counter[0] += 1
            if left[i] <= right[j]:
                out.append(left[i]); i += 1
            else:
                out.append(right[j]); j += 1
        return out + left[i:] + right[j:]

sort(data)
    return counter[0]

def duplicate_pairs(n):
    items = list(range(n))
    steps = 0
    for i in range(n):
        for j in range(i + 1, n):
            steps += 1
            if items[i] == items[j]:
                return steps
    return steps

def triple_checks(n):
    steps = 0
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                steps += 1
    return steps

def fib_calls(n):
    calls = [0]

def fib(k):
        calls[0] += 1
        return k if k < 2 else fib(k - 1) + fib(k - 2)

fib(n)
    return calls[0]

def classify(sizes, counts):
    growth = counts[-1] / counts[0]
    scale = sizes[-1] / sizes[0]
    exponent = math.log(growth) / math.log(scale)
    for limit, label in [(0.05, "O(1)"), (0.30, "O(log n)"), (0.75, "O(sqrt n)"), (1.07, "O(n)"),
                         (1.40, "O(n log n)"), (2.40, "O(n^2)"), (3.40, "O(n^3)")]:
        if exponent < limit:
            return label
    return "worse than polynomial"

LAB = [
    ("first item", first_item, [1000, 2000, 4000, 8000]),
    ("binary search, missing target", binary_search_worst, [1000, 2000, 4000, 8000]),
    ("linear search, missing target", linear_search_worst, [1000, 2000, 4000, 8000]),
    ("merge sort comparisons", merge_sort_comparisons, [1000, 2000, 4000, 8000]),
    ("all pairs, no duplicate", duplicate_pairs, [100, 200, 400, 800]),
    ("all triples", triple_checks, [20, 40, 80, 160]),
    ("naive fib calls", fib_calls, [10, 12, 14, 16]),
]

# Stretch A: space, measured as the deepest chain of open calls.
def depth_fact(n):
    deepest = [0]

def fact(k, depth):
        deepest[0] = max(deepest[0], depth)
        return 1 if k <= 1 else k * fact(k - 1, depth + 1)

fact(n, 1)
    return deepest[0]

def depth_bsearch(n):
    deepest = [0]
    items = list(range(n))

def search(lo, hi, depth):
        deepest[0] = max(deepest[0], depth)
        if lo > hi:
            return -1
        mid = (lo + hi) // 2
        if items[mid] < n:
            return search(mid + 1, hi, depth + 1)
        return search(lo, mid - 1, depth + 1)

search(0, n - 1, 1)
    return deepest[0]

# Stretch B: amortised cost of appending to a doubling array.
def cost_per_append(n):
    capacity, size, total = 1, 0, 0
    for _ in range(n):
        total += 1
        if size == capacity:
            total += size
            capacity *= 2
        size += 1
    return total / n

def print_report():
    print(f"{'function':<32}{'counts':<42}class")
    for name, fn, sizes in LAB:
        counts = [fn(n) for n in sizes]
        print(f"{name:<32}{str(counts):<42}{classify(sizes, counts)}")

def print_space():
    sizes = [100, 200, 400, 800]
    print()
    print("recursion depth (space)")
    for name, fn in [("recursive factorial", depth_fact), ("recursive binary search", depth_bsearch)]:
        counts = [fn(n) for n in sizes]
        print(f"{name:<32}{str(counts):<42}{classify(sizes, counts)}")

def print_amortised():
    print()
    print("amortised append cost")
    for n in [10, 1000, 100000]:
        print(f"n = {n:<8} cost per append = {cost_per_append(n):.3f}")

if __name__ == "__main__":
    print_report()
    print_space()
    print_amortised()

function                        counts                                    class
first item                      [1, 1, 1, 1]                              O(1)
binary search, missing target   [10, 11, 12, 13]                          O(log n)
linear search, missing target   [1000, 2000, 4000, 8000]                  O(n)
merge sort comparisons          [8715, 19419, 42856, 93640]               O(n log n)
all pairs, no duplicate         [4950, 19900, 79800, 319600]              O(n^2)
all triples                     [1140, 9880, 82160, 669920]               O(n^3)
naive fib calls                 [177, 465, 1219, 3193]                    worse than polynomial
 
recursion depth (space)
recursive factorial             [100, 200, 400, 800]                      O(n)
recursive binary search         [8, 9, 10, 11]                            O(log n)
 
amortised append cost
n = 10       cost per append = 2.500
n = 1000     cost per append = 2.023
n = 100000   cost per append = 2.311

Some design choices worth noticing:

Every counter is an integer, never a time. That makes the output identical on every machine.
LAB is a table, so adding a function means adding one tuple. The report code does not change.
classify returns the label of the first cut-off the exponent is below, so the cut-off list must stay in increasing order.
merge_sort_comparisons seeds the random generator with n. Without a seed, counts would change slightly from run to run, although the class would not.
The recursion-depth functions pass depth down instead of reading the stack, which makes the measurement portable.

Model answers to Part D