A vocabulary for describing how badly a program slows down as its input grows — and a proper look at recursion.
Everything from here on depends on being able to say how expensive a piece of code is. Do not rush this stage. It is short in weeks and heavy in leverage.
Why this stage exists
Without this vocabulary, every later choice is guesswork. With it, you can look at a piece of code and predict whether it will survive real data — which is the difference between something that works on your laptop and something that works in production.
What you are learning — 3 topics
Big-O notation
A growth forecast: it tells you what extra data will do to the amount of work, not how fast one laptop happens to be today.
Reach for it whenUse it before choosing an approach that will run on growing data; compare growth shapes instead of timing a tiny sample.
Think of it likeSaying a journey “takes twice as long if you double the distance” rather than “takes 43 minutes”. The first statement is still true on a different day in a different car.
You are not measuring seconds. Seconds depend on your laptop, on what else is running, and on the weather inside the processor. Big-O describes the shape of the growth, which is the part that stays true everywhere.
The handful you actually need, from best to worst. O(1): constant — the same time no matter how much data, like fetching item number 500 from a list. : grows extremely slowly, because each step throws away half of what is left; going from a thousand items to a million adds only about ten steps. O(n): grows in step with the data — reading every item once. O(n log n): the realistic best for sorting things. O(n²): a loop inside a loop, where ten times the data means about a hundred times the work.
Syntax you can use
for item in items:
One pass over the input: the usual O(n) shape.
for left in items:
for right in items:
Compares every pair: O(n squared), which becomes expensive quickly.
items.sort()
Sorts a list in O(n log n) time in the usual case.
while low <= high:
mid = (low + high) // 2
if items[mid] < target:
low = mid + 1
else:
high = mid - 1
Halves the remaining search space each turn: O(log n).
The same axes for every class. O(n squared) leaves the chart while O(log n) stays near the floor — that gap is why the notation matters.
Several ways to see it
Why it existsIt exists because seconds lie
Timing a run tells you about your laptop that afternoon, not about the code. Two machines disagree, and a faster machine hides a worse . Big-O throws away the hardware and keeps only the part that travels: how the work grows.
Its shapeYou are reading a curve, not a number
Every complexity class is the shape of a line on a graph of data against work. O(1) is flat, O(log n) barely lifts, O(n) is a diagonal, and O(n squared) turns upward and leaves the chart. Recognising the shape is the whole skill.
How it breaksIt says nothing about small inputs
Big-O describes behaviour as data grows, so it ignores constant factors entirely. An O(n) function with heavy setup can lose to an O(n squared) one on ten items. Use it to predict the cliff, not to micro-optimise a small list.
The Python you typeA loop inside a loop is the tell
In Python, one pass over the data is O(n). A nested loop over the same data is O(n squared). A halving step such as a is O(log n), and a sort is O(n log n). Reading nesting depth catches most cost mistakes before they ship.
In the wild
PostgreSQL query planner — compares estimated row counts and operation costs to choose a query plan.
React reconciler — keeps child reconciliation close to one pass so a large component tree remains responsive.
Python's Timsort — sorts lists in O(n log n) worst-case time rather than repeatedly comparing every pair.
Commonly gets misread as
"Big-O is a stopwatch." Correction: it describes how work grows, so constants and small inputs still matter.
"O(n) is always faster." Correction: it wins at scale, not necessarily on a ten-item input.
It is a function leaving itself a smaller copy of the same job, while the computer remembers the unfinished copies.
Reach for it whenReach for it when the data naturally contains smaller versions of itself, such as folders or nested JSON; use an explicit stack when depth can be huge.
You met the idea in week 13. Now look at the machinery. Every time a function is called, the computer sets aside a small area holding that call's own variables. That area is a , and the pile of them is the .
Frames are only released when a call finishes. So a recursive function that goes 10,000 deep has 10,000 frames alive at once, each using real memory. That is why depth is not free, and why Python stops you at around a thousand deep rather than letting the program consume all available memory.
Syntax you can use
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)
The recursive shape: stop at a base case, then make one smaller call.
from functools import cache
Imports the decorator that remembers repeated recursive subproblems.
@cache
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
Caches Fibonacci results so each n is calculated once.
stack = [root]
Starts an explicit stack, the loop-friendly replacement for deep recursion.
Notice that every unfinished multiplication occupies a frame until the base case starts the returns.
Several ways to see it
What the machine doesThe return address is part of every frame
A recursive call must preserve not only local values but the exact instruction where its caller will resume. When the returns, the machine restores those saved positions one frame at a time.
Against the alternativeAn explicit stack moves the same bookkeeping into your data
Depth-first recursion and a loop with a stack visit the same pending work in the same order. The loop is longer but avoids Python's recursion limit and lets you inspect, pause, or serialize the frontier.
How it breaksBalanced work can still overflow on a crooked input
A tree algorithm may be logarithmic on a balanced tree yet recurse once per node on a one-sided tree. Python does not optimize tail calls, so even a final recursive call consumes another frame.
In the wild
Git — walks commit-parent links to answer history and merge-base questions.
React reconciler — walks nested component children while building and comparing a UI tree.
Python's json module — descends into nested objects and while encoding or decoding values.
Commonly gets misread as
"Recursion is more powerful than a loop." Correction: the same work can be written with a loop and an explicit stack.
"The base case is optional cleanup." Correction: it is the stop sign that prevents unbounded calls.
What it costsEach call costs one stack frame of memory. A recursion n levels deep uses O(n) memory even if it does barely any work per level.
These are a few practical counting tools for splitting work, wrapping numbers, and noticing when is impossible.
Reach for it whenUse logarithms for repeated halving, remainders for wrapping or bucketing, and counting estimates before committing to exhaustive search.
Logarithms sound intimidating and are simple in this context: the logarithm of a number is roughly how many times you can halve it before reaching one. A million halves down to one in about twenty steps. That single fact is the entire reason binary search and balanced trees are fast, so it is worth having properly rather than approximately.
Modular arithmetic is the remainder operator you already met, taken seriously. It is clock arithmetic — after 12 comes 1 again. use it to fold any number down into a valid slot position, which is what makes dictionaries work.
Syntax you can use
import math
Imports the standard library's number helpers.
n % 2 == 0
Tests whether n is even.
math.gcd(a, b)
Finds the greatest common divisor, useful for simplifying fractions and cycles.
math.lcm(a, b)
Finds the least common multiple.
pow(base, exponent, modulus)
Computes a power modulo modulus without constructing the huge full power.
Notice that doubling the number of leaves adds only one decision level; that is the geometric source of log n.
Several ways to see it
Its shapeLogarithms count levels, not mysterious symbols
Repeated halving draws a tree whose depth is logarithmic: each new level doubles how many original items it can cover. A million leaves therefore need only about twenty binary decisions from root to leaf.
What the machine doesRemainders fold an unbounded number into a fixed range
`value % size` maps any integer onto one of `size` positions and repeats in a cycle. The machine computes a division remainder; the algorithm uses that cycle for clocks, circular buffers, and buckets.
How it breaksCounting can reject an algorithm before coding starts
Fifty yes-or-no choices create over a quadrillion combinations. Estimating the search space first prevents spending hours optimizing a brute-force program that cannot finish within a human lifetime.
In the wild
Python dictionaries — use hash values and table-size arithmetic to place keys into buckets.
TLS public-key cryptography — relies on arithmetic properties of large prime numbers.
Consistent hashing — uses modular positions on a ring to spread keys across servers.
Commonly gets misread as
"You need advanced maths for algorithms." Correction: most everyday choices need only counting, halving, and remainders.
"Trying every option is safe if the code is fast." Correction: combinations grow too quickly for hardware to rescue.
Reading about this stage is not the same as finishing it. Type every one of these from a blank file rather than copying — the writing is the part that teaches.
Audit your own old code
Take three programs you wrote in the first thirteen weeks and write down the Big-O of each, with one sentence justifying it. Your multiplication table printer is O(n²) — make sure you can say why. This is more valuable than any textbook exercise, because it is your own code.
Three recursive functions
Write recursive factorial, recursive Fibonacci, and a function that adds up the sizes of every file in a folder and its subfolders. For each, say how deep the call stack gets. The Fibonacci one is deliberately included because it is catastrophically slow — work out why before you reach week 33.
You are done with this stage when
Exit checkGiven any function you have written, you can state its Big-O and justify it in one sentence. You can write recursive factorial, Fibonacci and a directory-size function, and explain how the call stack behaves in each.
If you cannot do this, repeat the stage rather than moving on. Nothing later gets easier by skipping it.
This stage corresponds to DSA Phase 1 — Foundations & Complexity Analysis in the source roadmap.