Branch: Computer Science Foundations (quant-cs, Quant-Code region) · Node CS1.04 · ~22 focused hours · Gate ≥ 85% (quiz + code pack)

Somewhere in your near future is a script that works perfectly on the twenty-row sample you tested it on, and then seizes up (minutes of spinning, or a crash, or an answer that is silently wrong) the moment you point it at ten years of daily prices across five hundred tickers. This is not bad luck and it is not a Python problem. It is the single most common gap between "I can write code that runs" and "I can write code that survives contact with real data," and it has a name, a vocabulary, and a learnable set of habits. That is what this module installs. Not a list of algorithms to memorize: CS1.05, the next node in this branch, will give you the full toolbox of arrays, hash maps, trees, and sorting routines, but the thinking that lets you look at a piece of code, before you have run it on anything, and predict how its cost will grow as the input grows. That prediction is what separates an analyst who codes from a programmer who understands what they built.

Two ideas carry the whole module. The first is recursion: a function that solves a problem by calling a smaller version of itself, until the problem is small enough to answer directly. Recursion is not a trick or a party piece, it is often the most natural way to describe a computation that is self-similar (a sum of a list is "the first element plus the sum of the rest"; the value of a compounding deposit after n periods is "one period of growth applied to the value after n-1 periods"), and understanding it precisely is what lets you read and write a large fraction of the interesting code you will meet from here on, including most of CS1.05's data-structure algorithms. The second idea is Big-O notation, the vocabulary for describing how a computation's cost, time or memory, grows as its input grows, independent of which laptop you happen to be running it on today. Here is the whole module compressed into one sentence you will spend twenty-two hours earning the right to believe: an algorithm's Big-O class is a property of its shape, not a measurement of today, it tells you nothing about how many seconds your code takes on the data sitting in front of you right now, and everything about whether it will still be usable when that data is ten times, or ten thousand times, larger. Code that "works" on a small test and code that "scales" are different claims, verified by different means, and this module teaches you to tell them apart before production does it for you.

One promise for the hours ahead: by the end you will be able to take a piece of working Python (yours, a colleague's, or an AI coding assistant's) and, without running it, state its time and space complexity, name the exact operation that will make it slow at scale, and rewrite it to remove that operation. You will do this on both an India (₹) and a US ($) finance-flavored problem, and you will verify every claim by measurement, not by vibes. That reflex (read the shape, predict the growth, then measure to confirm) is worth more than any specific algorithm you memorize, because it is the reflex that tells you which algorithm to reach for in the first place.

Learning objectives

By the end you can:

Decompose a problem into precise, orderable steps before writing any code, and trace a short algorithm by hand (on paper, one step at a time) before trusting a program's output.
Write and read recursive functions: identify the base case and the recursive case in any recursive function, and explain precisely why omitting either produces either an immediately wrong answer or unbounded recursion.
Trace a recursive call by hand as a call stack (a stack of paused, waiting calls) and predict, before running the code, the exact order in which those calls complete and return.
State and derive Big-O time complexity: recognizing and deriving O(1), O(log n), O(n), O(n log n), O(n²), and exponential growth from a piece of code by counting operations as a function of input size n, not by guessing from how the code "feels."
Recognize space complexity, especially a recursive function's call-stack depth, as real memory cost, and predict when a correct recursive definition will crash on realistic input (RecursionError) long before it produces a wrong answer.
Diagnose and fix the classic recursion/Big-O bugs: a missing or unreachable base case, a hidden O(n) operation buried inside a loop that silently turns O(n) into O(n²), and the mutable-default-argument bug that corrupts naive memoization.
Reduce a naive O(n²) nested-loop solution to a faster one (an O(n) single pass, or an O(n log n) sort-based approach) by naming precisely which redundant work the nested loop repeats.
Profile Python code empirically: time it as input size grows, and connect the observed growth curve back to the theoretical Big-O class, understanding that Big-O and wall-clock time are related but different questions, answered by different kinds of evidence.
Dissect at least one India (₹) and one US ($) finance-flavored problem end to end: state its Big-O, implement both a correct and, where relevant, a faster version, and verify both against hidden tests that defeat a hardcoded answer.
(Productivity objective: R10 duality.) Use an AI coding copilot to accelerate writing and reviewing recursion- and complexity-sensitive code, without skipping the by-hand understanding step, and verify its output exactly as you verify your own: trace it, run the tests, and confirm it is not calling something that does not exist.

The duality, stated once (R10). Objectives 1–9 are the understanding objective the mastery gate rewards: you pass by demonstrating, closed-book, that you can derive complexity and trace recursion yourself. Objective 10 is the productivity payoff you keep afterward: once you can do the by-hand version, a copilot legitimately makes you faster at the mechanical parts. A tool can draft a recursive function for you; it cannot install the judgment to know whether that function terminates on every input, and that judgment is the entire content of this module.

Prerequisites & connections

Builds on. This is the fourth node of the quant-cs branch, and it assumes real comfort with CS1.01 (Python I, values, variables, control flow, functions, I/O) and CS1.02 (Python II, data structures, pure functions, idiomatic Python): you should already be fluent writing, calling, and returning from functions, and comfortable with lists, dicts, and basic control flow, because recursion is functions calling functions and you cannot reason about a call stack you cannot yet read. CS1.03 (how computers really work) is a close and recent neighbor: its treatment of the stack as literal, finite memory is exactly what turns "the call stack" from a metaphor in this module into a mechanical fact you already believe, and its Python memory experiments (id, sys.getsizeof) are the same instinct (inspect the machine, don't guess) that this module applies to time and space cost instead of memory layout. Per R11 (the branch's day-one-entry rule), the very first node of this branch, CS1.01, unlocks with no finance-phase prerequisite at all; within the branch, however, the chain is sequential, and CS1.04 assumes CS1.01–CS1.03 are done.

Feeds forward. Everything downstream of here leans on this module without re-teaching it. CS1.05 ( crown, Data Structures & Algorithms) is the direct continuation: it hands you arrays, hash maps, stacks, queues, trees, heaps, and graphs, and asks you to search, sort, and apply dynamic programming, greedy methods, and divide-and-conquer to finance-flavored problems, every one of those techniques is evaluated using the Big-O vocabulary and implemented using the recursion discipline this module builds; CS1.05 does not re-explain what a base case is. CS2.06 ( crown, Software Engineering & AI-Assisted Dev) assumes you can already look at a function, including one an AI assistant just wrote for you, and ask "what is this going to cost at scale?" before you decide it is safe to ship; that instinct is installed here, not there. Further out, every module in the quant-ds and quant-dev branches, a pandas pipeline running over ten years of daily data across hundreds of tickers, a backtest looping over years of trades, a signal computed cross-sectionally over a universe of thousands of names, silently assumes you will notice when a piece of that pipeline is quietly O(n²) and will melt down long before the loop finishes. This module is where that instinct is born.

Cross-links. This module carries no cross-link to G1's QM branch, the C-3 statistics/ML boundary (QM owns concepts, quant-ds owns implementation) governs the data-science modules further down this branch (DA1.05 onward), not algorithmic foundations. The one durable cross-link worth naming now: CS1.03's stack/heap material is the mechanism this module's "call stack" and "space complexity" sections lean on directly, if either concept feels shaky, that is the place to revisit, not a new topic to relearn here.

Core teaching content

Thinking algorithmically before you type a single line

An algorithm is nothing more than a precise, finite, orderable sequence of steps that turns an input into an output, and the discipline this module opens with is refusing to write code until you can state that sequence in plain language or on paper first. This sounds slow. It is the opposite of slow, because a bug caught in a paper trace costs you thirty seconds, and the same bug caught by a confusing runtime error costs you twenty minutes of guessing. Concretely: before writing compound_value, state in words what it does for the smallest possible input ("with zero periods left, the value is just the principal, unchanged") and what it does for one more period than that ("apply one period of growth, then solve the same problem with one fewer period remaining"). Every recursive function in this module is built from exactly that two-part sentence, and if you cannot say it in words, you are not ready to write it in Python, the code will not save you.

This module treats "trace it by hand first" as load-bearing, not optional classroom ritual. A hand trace is a table: one row per step, columns for whatever state changes (the current arguments, a running total, the loop counter). You will build several of these in the Worked Examples below, and the Practice Set expects you to build your own without being shown the table structure first. This is the same muscle a professional developer uses when reading someone else's code (or an AI assistant's) before trusting it: read it as a sequence of state changes, predict the next one, then check.

Recursion: a function that calls itself

A recursive function is a function defined, in part, in terms of a smaller call to itself. The simplest honest example is computing a value that compounds: the value of a deposit after n periods is one period of growth applied to its value after n − 1 periods, and the value after 0 periods is just the starting principal, full stop, with nothing left to compute. Written as code:

def compound_value(principal, rate, periods):
    if periods == 0:
        return principal
    return compound_value(principal * (1 + rate), rate, periods - 1)

Read this as two separate promises. The base case (if periods == 0: return principal) is the smallest input the function can answer directly, with no further recursive call, the floor the recursion stands on. The recursive case is everything else: it does one unit of work (principal * (1 + rate), one period of growth) and then hands off a strictly smaller version of the same problem (periods - 1) to another call of the same function. Every correct recursive function you will ever write is this same shape: solve the smallest case directly, and for everything else, do a little work and delegate a smaller version of the problem to yourself.

This is not a stylistic choice you can skip. A function with a recursive case but no base case, or a base case that some inputs can never reach, does not "recurse a lot", it recurses forever, until Python's own safety limit stops it with a crash. Section "The two things every recursive function needs" below makes this failure mode concrete; hold onto the two-part shape until then.

Tracing a recursive call by hand: the call stack as paused index cards

To actually believe recursion works, trace compound_value(1000, 0.05, 2) by hand, one call at a time. Picture each call as an index card: writing a card down is a Python call beginning; the card sits in a pile, paused, waiting; a card is removed from the pile only once its call has an answer.

Card 1: compound_value(1000, 0.05, 2). periods is 2, not 0, so this card cannot finish yet, it computes 1000 * 1.05 = 1050, and needs the answer to compound_value(1050, 0.05, 1) before it can return. It stays on the pile, paused, waiting.
Card 2: compound_value(1050, 0.05, 1). Same story: periods is 1, not 0. It computes 1050 * 1.05 = 1102.5 and needs compound_value(1102.5, 0.05, 0). It, too, stays on the pile, paused.
Card 3: compound_value(1102.5, 0.05, 0). Now periods == 0, the base case fires. This card needs no further call: it returns 1102.5 immediately and is removed from the pile.
Card 2 was waiting on exactly that value. It receives 1102.5, has nothing further to do with it (its own return statement is that recursive call), and returns 1102.5 itself. Removed from the pile.
Card 1 receives 1102.5 from card 2, returns it unchanged, and is removed. The pile is empty. The final answer, 1102.5, is what the very first call returns to whoever called it.

This is the call stack: the pile of paused, waiting calls, each one holding its own private copies of its arguments (principal, rate, periods), each unable to finish until the call it is waiting on finishes first. The stack grows by one card per recursive call going "down" into smaller subproblems, and shrinks by one card per return coming back "up." Notice something precise about this particular function: all of the arithmetic happens on the way down (principal * (1 + rate) is computed before the recursive call is made, as part of building the next call's arguments), the way back up does no further work at all, it just passes the same final number back through every waiting card unchanged. Not every recursive function is built this way; contrast this with a function that sums a list, where the addition happens on the way back up, once the recursive call returns a value to add to. Both shapes are correct recursion; noticing which shape you have is exactly the kind of precise reading this module is training. This exact function is Exercise CS1.04-e01 in the code pack, go trace one more period by hand before you open it.

The two things every recursive function needs

State this as a checklist, because "code review yourself against a checklist" is a durable habit, not a one-time insight:

A base case that is actually reachable. Not merely present in the code, reachable from every legal input the function will ever be called with. if periods == 0: return principal is fine when periods only ever starts non-negative and decreases by exactly 1 each call; it silently breaks if a caller ever passes a negative periods (periods goes -1, -2, -3, …, sailing past 0 forever and never equalling it), because the base-case condition was never designed for that input.
A recursive case that makes real progress toward the base case, for every input the function might see. "Real progress" means the argument that controls termination is provably getting closer to the base case's target, not merely changing. A function whose recursive step sometimes leaves its controlling argument completely unchanged for certain inputs (a bug you will spot deliberately in Practice Problem 15) has all the right code shape and none of the guarantee.

Miss either one and the symptom is the same: the call stack grows without bound. Python is not willing to let this run forever, it enforces a hard ceiling on how many calls may be paused, waiting, at once, and raises RecursionError: maximum recursion depth exceeded the instant that ceiling is crossed. As of this Python release the default ceiling, readable via sys.getrecursionlimit(), is 1,000, a number you can and should check for yourself (import sys; print(sys.getrecursionlimit())), because Python has changed this default before and may again; treat "1,000" as this module's dated, verify-it-yourself figure, not a law of the language. Getting RecursionError is not a mysterious crash, it is the direct, mechanical consequence of a call stack that a base case never stopped from growing, and diagnosing it starts by asking exactly the two questions in this checklist.

{
  "skill": "Using an AI pair-programmer (copilot) to write a recursive function — without letting it think for you",
  "use": "After you have written the base case and recursive case yourself, by hand, for a small example, and traced it on paper, ask a coding assistant to draft the full function or to suggest an edge case you may have missed — so you move faster on the mechanical part once the thinking is already done.",
  "tools": ["GitHub Copilot / Cursor — inline code-completion inside an editor", "Claude / ChatGPT — chat-based code drafting"],
  "prompt": "I have written this recursive function by hand: <YOUR CODE>. It is meant to handle <BASE CASE> and <RECURSIVE CASE>. Review it for an edge case I may have missed (empty input, a negative or already-base-case input, an off-by-one in the recursive step), and suggest one test I have not written. Do not rewrite my approach from scratch — critique what I already have.",
  "verify": "Read every line the tool produced before running it — never paste code you have not traced by hand at least once. Run this module's own hidden tests against it (the CS1.04 code pack grades exactly this way, with tests you never see). Confirm any function, method, or default-argument pattern it used genuinely exists and behaves as claimed — check the official Python documentation, not the assistant's confident say-so, since a hallucinated standard-library call is one of the most common failures in AI-drafted code.",
  "diy": "You must already be able to write a base case and a recursive case yourself and trace a small call on paper before reaching for this — that is exactly what the two sections above build. A copilot can accelerate the typing; only tracing the call stack yourself installs the judgment of 'does this call make real progress toward the base case?'",
  "market": "IN"
}

Big-O notation: describing growth, not seconds

Now the second pillar. Big-O notation describes how the cost of an algorithm (usually time, sometimes memory) grows as the size of its input, universally called n, grows, and it deliberately throws away two things that do not affect the shape of that growth: the exact constant multiplier (how fast your specific machine executes one operation) and lower-order terms that become irrelevant once n is large. The method for deriving it is mechanical, not intuitive: count the operations a piece of code performs as a function of n, then keep only the term that dominates as n gets large.

Take the smallest possible example:

def first_element(prices):
    return prices[0]

This does exactly one operation regardless of whether prices has 3 elements or 3 million, its cost is O(1), constant time, because n does not appear in the operation count at all. Contrast:

def total(prices):
    running = 0
    for p in prices:
        running += p
    return running

This performs exactly one addition per element, so the operation count is n, and the cost is O(n), linear time, twice the input, twice the work, no more and no less. The mechanical habit to build here, and to use for the rest of this module (and the rest of this branch): write down, as a formula in n, exactly how many times the expensive operation runs, then name the Big-O class that formula belongs to. Guessing "it's just one loop, so it must be fast" is exactly the instinct this module is training you out of. Worked Example 2 below and Common Mistake 2 both show precisely how that instinct fails.

The complexity ladder, with real numbers

Six growth classes cover the overwhelming majority of code you will write or read in this program, ordered from cheapest to most catastrophic, together with the concrete, verified operation counts they imply at four input sizes:

Class	Meaning	Everyday example	n=10	n=100	n=1,000	n=1,000,000
O(1)	constant, independent of `n`	reading `prices[0]`	1	1	1	1
O(log n)	halves the problem each step	binary search	≈3.3	≈6.6	≈10.0	≈19.9
O(n)	one pass over the input	summing a list	10	100	1,000	1,000,000
O(n log n)	a pass, `log n` times over (typically: sort, then scan)	`sorted(prices)`	33	664	9,966	≈19,931,569
O(n²)	every pair of elements	naive nested loop over all pairs	100	10,000	1,000,000	1,000,000,000,000
exponential (e.g. ≈φⁿ or 2ⁿ)	branches on every element, no reuse	naive recursive Fibonacci (below)	177 (n=10, exact)	astronomically large	:	:

Two things in this table are worth sitting with. First, O(log n) barely moves: multiplying n by a thousand, from 1,000 to 1,000,000, moves the O(log n) column from 10.0 to only 19.9, this is the entire reason binary search remains fast on enormous datasets, and it is why Worked Examples 4 and 5 (below) both lean on it. Second, the gap between O(n) and O(n²) is not a constant gap you can out-clever with a faster machine, it widens without bound as n grows: at n=1,000 the O(n²) column is already a thousand times the O(n) column, and at n=1,000,000 it is a million times larger. No amount of hardware improvement closes a gap that keeps widening; only a different algorithm does. Every number in this table is a plain computation (n, n·log₂n, n²) you can and should reproduce yourself, nothing here is quoted from memory.

Reading loops (and nested loops) for their true cost

The mechanical counting method extends directly to loops that contain loops. A loop nested inside another loop, both running over the same n-length input, executes its innermost operation n × n = n² times:

def all_pairs(prices):
    pairs = []
    for x in prices:
        for y in prices:
            pairs.append((x, y))
    return pairs

For every one of the n values of x, the inner loop runs all n values of y, n repeated n times is n² appends, hence O(n²). This is the single most common complexity class an analyst introduces by accident, because "two loops" feels only twice as expensive as "one loop," and it is not, it is n times as expensive, and that factor grows with the data. The habit to build: whenever you see a loop, ask "does anything inside this loop's body itself scan across up to n items?" If the answer is yes, you very likely have O(n²) hiding inside code that looks like a single O(n) loop, a case study you will work through precisely in Common Mistake 2 and Practice Problem 6.

Recursion trees and the cost of forgetting: naive Fibonacci

Some recursive functions call themselves more than once per invocation, and this is where naive recursion's cost can explode. The textbook case is the Fibonacci sequence (fib(0) = 0, fib(1) = 1, and fib(n) = fib(n-1) + fib(n-2) for n ≥ 2) written the direct, "obvious" way:

def fib_naive(n):
    if n < 2:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

Trace fib_naive(4)'s call tree by hand and something alarming appears: fib_naive(4) calls fib_naive(3) and fib_naive(2); fib_naive(3) calls fib_naive(2) and fib_naive(1), a second, entirely separate copy of fib_naive(2), computed completely from scratch, with no memory that the first copy's answer already exists. Every subproblem below the top gets recomputed, repeatedly, and the number of recomputations grows explosively. The exact call count follows a clean identity (calls(n) = 2·F(n+1) − 1, where F is the ordinary Fibonacci sequence) which you can verify by hand at small n (calls(5) = 2·F(6) − 1 = 2·8 − 1 = 15) and which was confirmed by direct instrumentation for this module: fib_naive(30) performs exactly 2,692,537 calls, and fib_naive(32), measured directly on ordinary hardware, took 0.309 seconds to complete its 7,049,155 calls. Extend that identity to n = 300 and the naive call count is 2·F(301) − 1 ≈ 7.19 × 10⁶², a 63-digit number, and hopeless to compute in any amount of time this program will ever wait for. This is what "exponential" (more precisely, growth proportional to φⁿ, where φ ≈ 1.618 is the golden ratio, a tighter and more accurate statement than the commonly rounded "O(2ⁿ)," though both describe the same qualitative explosion) means in practice: not "slow," but structurally, catastrophically infeasible past a fairly small n.

The fix is memoization: remember every subproblem's answer the first time it is computed, and look it up instead of recomputing it.

def fib_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n < 2:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

Now each distinct value of n from 0 up to the target is computed exactly once (O(n) time) and fib_memo(300), measured directly for this module, returned its exact 66-digit answer (222232244629420445529739893461909967206666939096499764990979600) in 0.000165 seconds. Same mathematical definition, same correct answers, six orders of magnitude difference in call count at a fairly modest n, this is the module's single clearest demonstration that Big-O is not academic decoration; it is the difference between a program that returns and one that never will. Notice, too, the sentinel pattern memo=None rather than memo={} as the default, the next section explains precisely why that choice is not stylistic. This exact contrast is Exercise CS1.04-e03 in the code pack; its hidden tests include an input specifically chosen so that only a genuinely memoized solution completes in time.

Space complexity: the call stack is real memory

Time is not the only cost. Every paused call sitting on the call stack (every index card in the earlier analogy) occupies real memory for as long as it waits, and a recursive function's space complexity is usually dominated by its maximum stack depth: how many calls are simultaneously paused at the deepest point of the recursion. compound_value(principal, rate, periods) reaches a stack depth of periods + 1 at its deepest, so its space cost is O(periods), proportional to the input, exactly like its time cost. This matters because Python enforces a hard, finite ceiling on stack depth (the RecursionError limit from the earlier section), so a recursive function's space complexity is not an abstract accounting exercise, it is a direct prediction of whether the program can even finish running on data of a given size, independent of whether the underlying algorithm is otherwise correct and fast. A function that is a genuinely correct, O(n)-time, textbook-perfect piece of recursion can still crash outright on a large real input if its recursion depth crosses the interpreter's ceiling, which is exactly the failure Worked Example 6 and Exercise CS1.04-e06 walk through on a realistically sized daily-price series.

Profiling for real: measuring instead of guessing

Big-O is a theoretical prediction, derived by counting operations on paper. Profiling is the empirical check: actually run the code, on inputs of several different growing sizes, and measure how long it takes. The two answer related but genuinely different questions, and a careful engineer uses both. A minimal, honest profiling harness needs only the standard library:

import time

def time_it(fn, *args):
    start = time.perf_counter()
    fn(*args)
    return time.perf_counter() - start

Run a candidate function at, say, n = 1,000, 2,000, 4,000, and 8,000 (doubling each time), record the wall-clock time at each size, and look at the ratios between consecutive times. An O(n) function should see its time roughly double alongside n; an O(n²) function should see its time roughly quadruple each time n doubles ((2n)² = 4n²); an O(n log n) function sits in between, growing a little faster than linear. This is exactly the exercise the Applied Mini-Project below asks you to run for real, on both an India-flavored and a US-flavored synthetic price series, and it is worth internalizing the boundary precisely: Big-O tells you the shape of the growth curve before you have any data; profiling tells you whether the code you actually wrote matches the shape you predicted, on the machine you actually have. When the two disagree (your code was supposed to be O(n) but the measured times are quadrupling) the measurement is telling you something true about your code that the theory, applied to the wrong code, could not have caught: go back and recount the operations, because something you assumed was O(1) inside that loop probably is not (see Common Mistake 2 and 8, and the "in" gotcha of Practice Problem 6).

Choosing recursion vs. iteration like an engineer, not a purist

Recursion and iteration (loops) can very often express the same algorithm, and neither is inherently superior, the engineering judgment is knowing which cost each one is actually paying. A loop-based version of compound_value pays no call-stack cost at all and cannot hit RecursionError regardless of how large periods is:

def compound_value_iterative(principal, rate, periods):
    value = principal
    for _ in range(periods):
        value *= (1 + rate)
    return value

Both versions are O(n) in time; only the recursive version is O(n) in space on top of that, because only it accumulates paused calls. The rule of thumb this module leaves you with: reach for recursion when the problem is naturally self-similar and the depth is bounded by something small and known (a fixed number of compounding periods, a tree with a modest, bounded depth, a divide-and-conquer split that halves the input every level so the depth is only O(log n)), and reach for iteration whenever the recursion depth would be proportional to a large, data-driven n, exactly the situation in Exercise CS1.04-e06. This is not "recursion is bad", divide-and-conquer recursion that halves its input, like the binary search below, only ever reaches a depth of O(log n), which for a million-element input is about 20 paused calls, utterly harmless. It is "know which shape of recursion you have before you decide," and that, again, is a question this module has now given you the tools to answer by counting, not by guessing.

Divide and conquer, and measuring it: binary search

Binary search is the cleanest possible illustration of divide and conquer: given a list sorted in ascending order and a target value, compare the target to the middle element; if they match, you are done; if the target is smaller, the entire right half can be discarded in one step (everything there is even larger); if larger, discard the left half. Each comparison eliminates half of what remains, which is exactly the mechanism behind the table's O(log n) column above. An iterative version, instrumented to count its own steps:

def count_binary_search_steps(sorted_arr, target):
    lo, hi = 0, len(sorted_arr) - 1
    steps = 0
    while lo <= hi:
        steps += 1
        mid = (lo + hi) // 2
        if sorted_arr[mid] == target:
            return steps
        elif sorted_arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return steps

and its natural recursive twin, divide-and-conquer recursion, with a stack depth of only O(log n) since each call handles half the remaining range:

def binary_search_recursive(arr, target, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    if lo > hi:
        return -1
    mid = (lo + hi) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, hi)
    else:
        return binary_search_recursive(arr, target, lo, mid - 1)

are Exercises CS1.04-e04 and CS1.04-e05 respectively. A brief scope note, because this branch is careful about not duplicating itself: this module's job is to use binary search as a vehicle for seeing O(log n) directly, with your own instrumented step-counter; CS1.05's job is the fuller treatment of searching and sorting as a topic in its own right, alongside hash maps, trees, and the rest of the data-structure toolbox. Nothing here pre-empts that.

{
  "skill": "Using a copilot to go from a working O(n^2) solution to a faster one — safely",
  "use": "Once you already have a correct (even if slow) brute-force solution, and you can already state out loud why it is O(n^2), ask a coding assistant for a faster approach as a second opinion to weigh against your own reasoning — not as the first idea you reach for.",
  "tools": ["Claude / ChatGPT / Copilot Chat — ask for a complexity-improved version of a working function", "Any AI code reviewer that explains WHY a suggested change is faster, not just pastes different code"],
  "prompt": "Here is a correct O(n^2) function: <YOUR CODE>. I believe this can be done faster. Explain the technique in plain words first, with no code. Only once I confirm I understand the technique, show the implementation, and tell me which assumption the faster version relies on (e.g. sortedness, no duplicates, a single pass being sufficient) that the slow version did not need.",
  "verify": "Re-derive the new Big-O yourself by counting the operations in the returned code — do not accept the assistant's complexity claim at face value. Run it against this module's hidden tests, which include both an India- and a US-flavored synthetic price series, before trusting it. Specifically re-test the edge cases your original brute-force version handled correctly (an empty list, all-equal values, strictly decreasing values) to confirm the 'faster' version did not quietly trade correctness for speed.",
  "diy": "You must already be able to state, unprompted, why a nested loop over n items is O(n^2) before this callout is safe to use — that is exactly what the sections on loops and the complexity ladder above build. Ask an assistant for the trick only once you can already name the disease it is curing.",
  "market": "US"
}

Common mistakes & how experts think differently

"Recursion is always more elegant, so it's always the better choice." Elegance is a real virtue and not the only one. A recursive solution pays a call-stack cost a loop-based equivalent does not, Python performs no tail-call optimization (a recursive call that is the very last thing a function does still gets a fresh stack frame, unlike some other languages), and a "beautiful" recursive definition can crash outright on realistically sized input where an uglier loop would not. The expert asks two separate questions, "is this correct?" and "what does this cost, in both time and stack depth, at the n I will actually see?", and treats elegance as a tiebreaker between two answers that already satisfy the second question, never as a substitute for asking it.
"It's just one loop, so it's O(n)." A single for loop is O(n) only if every operation inside its body is itself O(1). The moment the loop body contains something that can itself scan up to n items, an x in some_list check, a .count(...), a nested search, the true cost is O(n) multiplied by that inner cost, frequently landing at O(n²) while the code still visually reads as "one loop." The expert's habit is to look inside every loop body and ask, of every single statement, "does this one line's cost depend on how much data has accumulated so far?"
"A missing base case just means it runs a bit longer." It means the call stack grows without limit until Python's recursion-depth ceiling forcibly stops it with RecursionError, not "slow," but "guaranteed to fail" on any input that doesn't accidentally happen to hit some other stopping condition first. The expert checks, for every recursive function, both that a base case exists and that every legal input can actually reach it, the second half is the one people skip, and it is the half that Practice Problem 15's flawed step-counter is built to catch you skipping.
Off-by-one errors in binary search's bounds. Using < where <= belongs (or the reverse) in the while lo <= hi condition, or writing mid (rather than mid + 1 / mid - 1) when narrowing the range, either infinite-loops on a range that never shrinks or silently skips the element you were searching for. The expert's defense is not "be more careful", it is to trace the smallest nontrivial cases by hand (a one-element array, a two-element array, the target as the very first or very last element) every single time a search's bounds are written or changed, because these are exactly the cases where boundary mistakes hide.
The mutable-default-argument bug: def f(n, memo={}). A default argument value is created once, at the moment the function is defined, not once per call, so a mutable default like {} or [] is silently shared and can accumulate state across calls that were supposed to be independent. This module's Fibonacci solution deliberately uses memo=None as a sentinel and creates a fresh dictionary inside the function body precisely to avoid it. The expert's rule, with no exceptions: default arguments should be immutable (numbers, strings, None, tuples), never a list or a dict: full stop.
Treating Big-O as a stopwatch reading. "O(n) is always faster than O(n²)" is only guaranteed for n large enough that the growth rate dominates the constant factors Big-O deliberately ignores; at small n, an O(n²) algorithm with a tiny constant factor can genuinely outrun an O(n) algorithm with a large one. The expert reads Big-O as answering "which one wins as n grows without bound," and reaches for profiling (the section above) to answer the separate, legitimate question of "which one is faster on the specific size of data I actually have today."
"Recursion depth is free, it's just a function call." Every paused call occupies real stack memory for as long as it waits, exactly as concretely as a list occupies heap memory, and Python enforces a hard, finite ceiling on how many calls may be paused simultaneously. The expert treats a recursive function's maximum depth as a space-complexity claim to be derived and checked against realistic input sizes, in exactly the same way they would check a list's memory footprint, not a detail that "the language handles."
Confusing "correct" with "efficient," and mistaking small-test success for scale-readiness. A brute-force O(n²) solution and its optimized O(n) sibling can return identical answers on every small test you happen to write, and diverge only in how long they take once n is large, which means passing your tests proves correctness, never efficiency. The expert's defense is exactly this module's central habit: derive the Big-O class by counting operations before trusting a small test suite's silence about performance, which is also precisely why this module's own code pack quietly grows its hidden tests' input sizes rather than keeping them the same size as the visible example.

The thread through all eight: the expert holds two separate, simultaneously true questions about any piece of code, "does it return the right answer?" and "what does returning that answer cost, and how does that cost grow?", and refuses to let a confident answer to the first question stand in for an answer to the second. That discipline, more than any specific algorithm, is what this module is installing.

Worked examples

Worked example 1: Tracing recursive compound growth by hand (India, ₹)

Meera is reviewing a teammate's function for a recurring-deposit calculator and wants to confirm, without running it, that compound_value(1000, 0.05, 3) returns the value everyone expects before she signs off on it. (All figures here are illustrative/synthetic, a stand-in recurring-deposit scenario, not a real reported product rate.)

Solution. Step 1, write the two-part definition in words first. "With zero periods left, the value is just the principal, unchanged. With more than zero periods left, apply one period of growth, then solve the same problem with one fewer period." This matches the code exactly: if periods == 0: return principal, else return compound_value(principal * (1 + rate), rate, periods - 1).

Step 2, trace the call stack, one card at a time. Card 1, compound_value(1000, 0.05, 3): not the base case; computes 1000 × 1.05 = 1050, defers to compound_value(1050, 0.05, 2), stays paused. Card 2, compound_value(1050, 0.05, 2): computes 1050 × 1.05 = 1102.5, defers to compound_value(1102.5, 0.05, 1), stays paused. Card 3, compound_value(1102.5, 0.05, 1): computes 1102.5 × 1.05 = 1157.625, defers to compound_value(1157.625, 0.05, 0), stays paused. Card 4, compound_value(1157.625, 0.05, 0): base case fires: returns 1157.625 directly, no further call.

Step 3, unwind, and notice what happens on the way up. Card 3 receives 1157.625 from card 4 and returns it, unchanged, since its own return statement is that recursive call with nothing further applied to the result. Card 2 receives 1157.625 from card 3 and likewise returns it unchanged. Card 1 does the same. The final answer, delivered to whoever called compound_value(1000, 0.05, 3) in the first place, is 1157.625.

Step 4: state the complexity. One stack frame per remaining period, one multiplication per frame: time complexity O(periods), space complexity O(periods) (the maximum simultaneous stack depth). Both are linear in the one number that actually varies here.

Read it. The precise thing to notice, and to carry forward: every unit of arithmetic in this function happens on the way down, while building each next call's arguments, the unwind phase does no computation at all, it just relays the same final number back through every waiting card. Not every recursive function is built this way (Worked Example 6 is not); recognizing which shape you have, before you trace it, is exactly the "think before you type" discipline this module opened with. This is Exercise CS1.04-e01 in the code pack, its hidden tests include a synthetic ₹2,50,000-scenario compounding at 8% for 3 periods and a synthetic $10,000 scenario at 4.5% for 5 periods, deliberately different numbers from this trace, so a solution that merely hardcodes 1157.625 fails immediately.

Worked example 2: Big-O of a single linear scan (US, $)

Owen is reviewing a colleague's one-line assertion that "this function is basically instant, it's just one loop" for a piece of code that counts how many days, out of a series of daily returns, exceeded some threshold. (Figures illustrative/synthetic, a stand-in US-style daily-return series, not a real reported series.)

def count_big_up_days(returns, threshold):
    count = 0
    for r in returns:
        if r > threshold:
            count += 1
    return count

Solution. Step 1, count the operations as a function of n. Let n be the length of returns. The loop body, one comparison, and possibly one increment, runs exactly once per element, with no operation whose own cost depends on how much of the list has already been processed. Total operation count: a small constant number of operations, times n. That is O(n) by definition: the cost of one iteration is O(1), and there are n iterations, so the whole function's cost is O(1) × n = O(n).

Step 2, name the exact instinct being corrected. "It's just one loop" is not wrong about the code's shape, it is wrong about what that shape implies for cost. O(1) describes the cost of a single pass through the loop body; the function's total cost multiplies that by the number of times the body runs. Confusing "each step is cheap" with "the whole function is cheap" is precisely the gap between O(1) and O(n).

Step 3, confirm by counting a concrete size. At n = 10,000 daily observations (roughly forty years of trading days, illustrative), this function performs on the order of 10,000 comparisons: fast, easily sub-millisecond on ordinary hardware, and (critically) the reason it is fast is exactly its O(n) shape, not an accident of this particular data size. Double n to 20,000 and the operation count doubles to roughly 20,000; this is the signature of linear growth, confirmable directly with the time_it profiling harness from the Core content above.

Read it. The instinct to fix is treating "one loop" as a synonym for "cheap." One loop over n items, doing O(1) work per item, is O(n), genuinely fast for the vast majority of real analyst workloads, but still a cost that grows, linearly, with the data, and worth distinguishing sharply from the O(1) that some people mean when they say "instant." Compare this directly against Worked Example 5 below, where a second loop nested inside the first turns this same shape into O(n²).

Worked example 3: The Fibonacci recursion tree, and what memoization actually buys you (neutral)

A learner is told "naive recursive Fibonacci is slow" and wants to see, in exact numbers rather than a vague gesture, what "slow" means and precisely what fixing it buys.

Solution. Step 1, build the smallest tree by hand. fib_naive(4) calls fib_naive(3) and fib_naive(2). fib_naive(3) calls fib_naive(2), a second, independent copy, and fib_naive(1). Already, by n = 4, fib_naive(2) has been computed twice, from scratch, with no memory that the first computation ever happened. Every level down repeats this doubling.

Step 2, use the exact identity, not a guess. The naive call count follows calls(n) = 2·F(n+1) − 1, where F is the ordinary Fibonacci sequence (F(0)=0, F(1)=1, F(2)=1, F(3)=2, F(4)=3, F(5)=5, F(6)=8, …). Check it at n = 5: F(6) = 8, so calls(5) = 2×8 − 1 = 15, verifiable by drawing all 15 calls in the tree by hand if you want to see every one. This identity was confirmed directly, not assumed, for every value used in this module: fib_naive(30) makes exactly 2,692,537 calls; fib_naive(32), timed directly on ordinary hardware, took 0.309 seconds for its 7,049,155 calls, and fib_naive(34) took 0.767 seconds for 18,454,929 calls.

Step 3, extend the identity to see where it becomes hopeless. At n = 300: calls(300) = 2·F(301) − 1 ≈ 7.19 × 10⁶², a 63-digit number of calls, and no computer will finish that count in any time this program will wait for. Contrast that with the memoized version: fib_memo(300), timed directly for this module, returned its exact 66-digit answer in 0.000165 seconds. Same mathematical function, same correct answer at every shared input, the only difference is whether each distinct subproblem is solved once (memoized, O(n) calls) or re-solved every time it is encountered (naive, ≈φⁿ calls, where φ ≈ 1.618, a tighter description than the commonly rounded "O(2ⁿ)," though both convey the same explosive shape).

Read it. "Slow" undersells this by a wide margin, naive Fibonacci past a fairly modest n is a program that will not finish before the heat death of anything you care about, while the identical function, memoized, is instantaneous at the same n. This is the single clearest number in the entire module for the claim that Big-O determines whether a program is usable, not merely how comfortable it is to wait for. This is Exercise CS1.04-e03; its hidden tests are specifically sized so that a correctly memoized solution finishes easily and a naive one has no realistic chance.

Worked example 4: Binary search over a sorted price table, traced (India, ₹)

Meera has a small sorted table of eight synthetic NSE-style closing levels, illustrative, not real reported data, [10, 20, 30, 40, 50, 60, 70, 80] (treat these as ₹ price levels), and wants to find the level 70 using binary search, tracing every step by hand first.

Solution. Step 1: set up the range. lo = 0, hi = 7 (the last valid index of an 8-element list), steps = 0.

Step 2: trace each iteration. Iteration 1: steps = 1; mid = (0 + 7) // 2 = 3; arr[3] = 40. Since 40 < 70, the target must be strictly to the right: lo = mid + 1 = 4. Iteration 2: steps = 2; mid = (4 + 7) // 2 = 5; arr[5] = 60. Since 60 < 70, narrow again: lo = 6. Iteration 3: steps = 3; mid = (6 + 7) // 2 = 6; arr[6] = 70, a match. Return steps = 3.

Step 3: confirm against the theoretical prediction. The complexity-ladder table predicts roughly log₂(8) = 3 comparisons for an 8-element sorted list in the worst case, and the hand trace lands on exactly 3, theory and trace agree, which is exactly the check a careful engineer runs every time a new piece of divide-and-conquer code is written.

Read it. Compare this to a linear scan over the same 8 elements, which in the worst case (target at the very end, or absent) checks all 8, nearly three times the work here, and the gap only widens as the table grows: at 1,024 sorted rows, binary search needs at most ⌈log₂ 1024⌉ = 10 comparisons where linear search might need all 1,024. This exact function, count_binary_search_steps, is Exercise CS1.04-e04; its recursive twin, binary_search_recursive, is Exercise CS1.04-e05, both graded with hidden tests built from a different, seeded synthetic sorted array on both an India- and a US-flavored fixture, defeating any solution that merely hardcodes 3 or 6.

Worked example 5: Collapsing a brute-force O(n²) scan into an O(n) pass (US, $)

Owen has a brute-force function that checks every pair of days in a US-style daily closing-price series to find the largest profit from buying on one day and selling on a strictly later day, and wants a faster version before running it on years of real-sized data. (Prices illustrative/synthetic.)

Solution. Step 1, see the brute force's true cost. Given prices = [100, 90, 95, 130, 80, 140] (six synthetic $ closing levels), the naive approach checks every pair (i, j) with i < j, with 6 elements that is 6×5/2 = 15 pairs, and keeps the largest prices[j] - prices[i]. Enumerating the profitable ones: (90, 95)→5, (90, 130)→40, (90, 140)→50, (95, 130)→35, (95, 140)→45, (80, 140)→60, and the rest are non-positive or smaller; the maximum is 60 (buy at 80, sell at 140). At n days this is O(n²): 15 pairs at n=6 becomes 1,000,000 pairs at n=2,000, a two-year daily series.

Step 2: name the redundant work. The brute force re-scans, for every later day j, every single earlier day i, but by the time you reach day j, you have already seen every price before it. The only fact about "every earlier day" that a later day's profit calculation actually needs is the single smallest price seen so far; re-checking each earlier day individually recomputes information you already possess.

Step 3, replace the inner loop with one running value. Track min_so_far (the lowest price seen up to, but not including, the current day) and best (the largest profit seen so far), updating both in a single left-to-right pass: for each price p, first check whether p - min_so_far beats best, then update min_so_far if p is itself a new low. On [100, 90, 95, 130, 80, 140]: start min_so_far=100, best=0; p=90: 90-100=-10, not better, min_so_far→90; p=95: 95-90=5>0, best→5; p=130: 130-90=40>5, best→40; p=80: 80-90=-10, not better, min_so_far→80; p=140: 140-80=60>40, best→60. Final answer: 60, identical to the brute-force result, computed with one pass instead of fifteen pair-checks, and the gap between "one pass" and "all pairs" only widens as n grows.

Read it. Nothing about the answer changed; only the amount of repeated work did. This is the general pattern behind reducing O(n²) to O(n): find the single running summary (here, "the minimum so far") that lets each new element be handled in O(1) additional work, replacing an inner loop that re-derives that summary from scratch every time. This exact function is Exercise CS1.04-e07; its hidden tests independently verify the fast version against a genuine brute-force reference computed on a different seeded price path for both an India- and a US-flavored series, so a fast solution that quietly drops correctness for speed fails immediately.

Worked example 6: When the call stack runs out: recursion depth on a real price history (neutral)

A learner has a recursive list-summing function that works perfectly in every test they wrote (all on lists of five or ten elements) and is confused when it crashes the first time it is pointed at five years of real daily data.

Solution. Step 1, the naive recursive shape. A direct, one-call-per-element recursive sum: sum the first element plus the recursive sum of the rest. Each call is paused, waiting on the next, exactly as in Worked Example 1, except here, unlike that example, one stack frame is created per element of the input, not per a small, fixed number of compounding periods.

Step 2, do the arithmetic on stack depth. Five years of daily trading data is on the order of 1,250 rows; a more conservative "long history" test used directly for this module's own hidden tests runs to 3,000 and 3,500 rows. Python's default recursion ceiling, confirmed directly via sys.getrecursionlimit(), is 1,000. A one-call-per-element recursive sum over a 3,000-element list therefore needs roughly 3,000 simultaneously paused calls, nearly three times the ceiling, and this was confirmed directly for this module: the naive recursive approach, run against a 3,000-element list, raises RecursionError: maximum recursion depth exceeded, every time, deterministically, regardless of what the list actually contains.

Step 3: diagnose correctly, then fix. This is not a bug in the arithmetic, the function's logic is entirely correct, and it would return the right answer if only the stack could hold enough paused calls. The failure is purely a space-complexity problem: O(n) stack depth, for an n that real data made too large. The fix is exactly the recursion-vs-iteration judgment from the Core content: rewrite the same computation as a loop, which holds no per-element stack frame at all and can walk a list of any length the machine's ordinary memory can hold.

def cumulative_return_path(daily_returns):
    result = []
    running = 1.0
    for r in daily_returns:
        running *= (1 + r)
        result.append(running)
    return result

Read it. The lesson is not "recursion is dangerous", it is that a recursive function's stack depth is a space-complexity claim with a hard, checkable ceiling, and that specific claim, not the function's correctness: is what breaks here. This exact contrast is Exercise CS1.04-e06; its hidden tests use series of 3,000 and 3,500 synthetic daily returns precisely because that size reliably exposes a naive recursive attempt while an iterative one handles it instantly.

Practice set

Work each problem fully (on paper first where a trace or a computation is involved) before reading its solution.

P1 (guided). Base case reachability. Consider def count_down(n):\n if n <= 0:\n print("liftoff"); return\n print(n); count_down(n - 1). Identify the base case and the recursive case. Then say what would happen if the base case condition were changed to n == 0 and the function were called as count_down(-3).

Solution. Base case: n <= 0 (prints "liftoff" and returns with no further call). Recursive case: prints n, then calls count_down(n - 1). With the condition changed to n == 0, calling count_down(-3) produces the sequence -3, -4, -5, …, decreasing by 1 each time, but starting below zero and moving further from zero, so it never equals 0 and never reaches the base case: this recurses without bound until RecursionError stops it. The lesson is exactly Common Mistake 3's second half: a base case must be reachable from every input actually passed in, not merely present in the code.

P2 (guided). Classify a single loop. What is the time complexity of total = 0; for x in items: total += x; return total, as a function of n = len(items)?

Solution. One addition per element, no operation whose cost depends on how much has already run: operation count is exactly n, so the complexity is O(n).

P3 (guided). Classify nested loops. What is the time complexity of appending (x, y) for every x in items and every y in items (a nested loop, both over the same n-length list)?

Solution. For each of the n values of x, the inner loop runs all n values of y: n × n = n² appends. O(n²).

P4. Trace by hand: compound_value(100, 0.10, 3). Build the full call-stack trace (as in Worked Example 1) and state the final answer and its time/space complexity.

Solution. compound_value(100, 0.10, 3) → computes 100 × 1.10 = 110, defers to compound_value(110, 0.10, 2) → computes 110 × 1.10 = 121, defers to compound_value(121, 0.10, 1) → computes 121 × 1.10 = 133.1, defers to compound_value(133.1, 0.10, 0) → base case, returns 133.1 directly. Unwinding returns 133.1 unchanged through every waiting card. Final answer: 133.1. Time and space complexity: O(periods) = O(3), i.e. linear in the number of periods.

P5. Binary search's worst case at n = 16. A sorted list has 16 elements. What is the maximum number of comparisons binary search will ever need?

Solution. ⌈log₂ 16⌉ = 4. Each comparison discards half the remaining range, and 16 halves to 8, to 4, to 2, to 1 in exactly 4 steps in the worst case.

P6. The hidden O(n) inside a loop. def has_duplicates(items):\n seen = []\n for x in items:\n if x in seen:\n return True\n seen.append(x)\n return False. This looks like a single O(n) loop. What is its actual worst-case time complexity, and why? Name one fix.

Solution. The loop itself runs at most n times, but x in seen is itself an O(k) operation, where k is however many items are already in seen (up to n − 1 by the last iteration), a list membership check scans the list from the start. In the worst case (no duplicates exist, so every check runs and every element gets appended), total work is 1 + 2 + … + (n-1) ≈ n²/2, i.e. O(n²), despite the code visually showing "one loop." Fix: replace the list seen with a set, whose membership check (x in seen) is O(1) on average, restoring the whole function to genuine O(n).

P7. Recursion depth budget. Python's default recursion limit is 1,000. If a function recurses exactly once per element of its input with no other nested calls, roughly what is the largest list it can safely sum this way without raising RecursionError?

Solution. Roughly just under 1,000 elements, in practice a bit less than the full 1,000, since a handful of stack frames are already in use (the interpreter, the calling code, the outermost call itself) before the recursion even starts, so treating something like 950–990 as the safe practical ceiling (without deliberately raising the limit) is the honest engineering answer, not a bare "1,000."

P8. Fibonacci call count via the identity. Using calls(n) = 2·F(n+1) − 1, how many calls does fib_naive(5) make? Show the Fibonacci values used.

Solution. F(6) = 8 (from F: 0, 1, 1, 2, 3, 5, 8, …), so calls(5) = 2 × 8 − 1 = 15.

P9. Spot the memoization bug. def add_item(item, basket=[]):\n basket.append(item)\n return basket. What does calling add_item('apple') and then, separately, add_item('banana') return each time, and why? How would you fix it?

Solution. add_item('apple') returns ['apple']; add_item('banana'), called separately, returns ['apple', 'banana'] (not just ['banana']) because the default list [] is created exactly once, when the function is defined, and is silently shared and accumulated across every call that relies on the default. (Confirmed directly: the second call's result still contains 'apple' from the first.) Fix: use basket=None as a sentinel and create a fresh list inside the function body when basket is None, the identical pattern this module's fib_memo(n, memo=None) uses for exactly this reason.

P10. Recursive to iterative. Given a one-call-per-element recursive function that finds the maximum of a list (def rec_max(items, i=0): ... recursing once per index), rewrite it as an equivalent loop, and state which cost changes and which does not.

Solution. Iterative version: def iter_max(items):\n best = items[0]\n for x in items[1:]:\n if x > best:\n best = x\n return best. Time complexity is unchanged, both are O(n). What changes is space complexity: the recursive version needs O(n) stack depth (one paused call per element) and risks RecursionError on a long list; the iterative version needs O(1) additional space (best alone) regardless of how long the list is.

P11. Big-O arithmetic at n = 1,000,000. Fill in the approximate operation count for each class at n = 1,000,000: O(log n), O(n), O(n log n), O(n²).

Solution. O(log n) ≈ 19.9 (≈20); O(n) = 1,000,000; O(n log n) ≈ 19,931,569 (about 20 million); O(n²) = 1,000,000,000,000 (one trillion). Notice the O(n²) column is a million times the O(n) column at this size, the gap this module keeps returning to.

P12 (India, ₹). Trace and classify. By hand, compute compound_value(200000, 0.06, 4) (₹2,00,000 growing at 6% for 4 periods, illustrative/synthetic), and state its time and space complexity.

Solution. 200000 × 1.06 = 212000 → 212000 × 1.06 = 224720 → 224720 × 1.06 = 238203.20 → 238203.20 × 1.06 = 252495.392. Final answer: ₹2,52,495.39 (rounded). Time and space complexity: O(periods) = O(4), linear in the number of compounding periods, identical in shape to Worked Example 1 and Practice 4.

P13 (US, $). Brute force vs. single pass, by hand. Given US-style closing prices [7, 1, 5, 3, 6, 4] (illustrative/synthetic), compute the maximum single-trade profit two ways: (a) by checking the key profitable pairs directly, and (b) by running the single-pass min_so_far/best trace. Confirm they agree, and state each approach's Big-O.

Solution. (a) Profitable pairs: buying at 1 and selling at 5 gives 4; buying at 1 and selling at 6 gives 5 (the best found by inspection); buying at 3 and selling at 6 gives 3; no other pair beats 5. (b) Single pass: min_so_far=7, best=0; p=1: not better, min_so_far→1; p=5: 5-1=4>0, best→4; p=3: 3-1=2, not better; p=6: 6-1=5>4, best→5; p=4: 4-1=3, not better. Final: 5, agreeing with (a). Brute force here is O(n²) (checking pairs); the single pass is O(n) (one left-to-right scan).

P14. Verify the Hanoi-style recurrence. The vault-transfer puzzle's move count satisfies T(n) = 2·T(n-1) + 1, with T(0) = 0. Compute T(1) through T(4) from the recurrence, and confirm each equals 2ⁿ − 1.

Solution. T(0)=0; T(1) = 2×0+1 = 1; T(2) = 2×1+1 = 3; T(3) = 2×3+1 = 7; T(4) = 2×7+1 = 15. Check against 2ⁿ−1: 2¹−1=1, 2²−1=3, 2³−1=7, 2⁴−1=15, all match. Each additional bar doubles the previous move count and adds one, which is exactly why the sequence explodes exponentially rather than linearly.

P15. Spot the non-terminating recursive step. def steps_to_one_buggy(n):\n if n == 1:\n return 0\n if n % 2 == 0:\n return 1 + steps_to_one_buggy(n // 2)\n else:\n return 1 + steps_to_one_buggy(n). For which inputs does this terminate, and for which does it recurse forever? Why?

Solution. It terminates for any n that is (or eventually becomes, through repeated halving) exactly 1 via the even branch. It never terminates for any odd n > 1, because the else branch calls steps_to_one_buggy(n) with the exact same n, no progress at all is made toward the base case, so an odd starting value greater than 1 recurses identically forever (confirmed directly: n = 7 stays at 7 every single step) until RecursionError intervenes. This is Common Mistake 3's second checklist item made concrete: a base case existing is not sufic ient, every legal input must actually be able to reach it, and this recursive step silently fails that for half of all integers.

P16. Why passing tests doesn't reveal Big-O. In two or three sentences, explain why "this code passed every test I wrote, all on inputs of size 20" tells you nothing about its Big-O class, and name the one thing that does.

Solution. Tests on a small, fixed input size verify correctness at that size (that the answer is right) and say nothing about how the cost changes as the size changes, because a slow O(n²) function and a fast O(n) function can return identical, correct answers on the same small input and differ only once n grows large. The one thing that reveals Big-O is counting operations as a function of n on paper (or, empirically, timing the same code across several genuinely different, growing values of n and observing the shape of the growth), never the silence of a test suite that only ever ran on one size.

Applied mini-project

Predict, then measure: closest pair of prices.

This project is the module's synthesis: implement two algorithms of different Big-O classes that answer the same question, predict before running anything which will win as data grows, then verify that prediction by actual measurement, the same "theory, then evidence" discipline as the Core content's profiling section, applied to a problem you have not already seen worked out above.

The problem. Given a list of prices, find the smallest absolute difference between any two of them (the "closest pair"). Implement it two ways:

Brute force, O(n²): check every pair (i, j) with i < j and keep the smallest abs(prices[i] - prices[j]).
Sort-then-scan, O(n log n): sort the list (Python's built-in sorted(), you are not implementing a sort algorithm here; that is CS1.05's job), then check only adjacent pairs in the sorted order. (Convince yourself in one sentence why this is enough: if the closest pair were not adjacent after sorting, some element strictly between them in sorted order would be even closer to at least one of them, contradicting that they were the closest pair.)

Do this, in order:

Implement both, and verify they agree on a small, hand-checkable list you can also solve by inspection (e.g. five or six values where you can eyeball the closest pair).
Predict, before measuring. Write down which of the two you expect to be faster at small n and at large n, and why, in terms of the two functions' Big-O classes, before you run a single timing.
Measure. Using the time_it pattern from the Core content, time both implementations on a synthetic India-flavored (₹) price list and a synthetic US-flavored ($) price list, at four sizes each, doubling every time (e.g. n = 200, 400, 800, 1,600), and record all eight timings (two implementations × four sizes) per market in a small table.
Classify from the data. For each implementation, look at how the timings change as n doubles, and state which Big-O class the measured growth resembles, quadrupling per doubling points to O(n²); a little more than doubling points to O(n log n).
Reflect and connect back. In three or four sentences: which of this module's eight code-pack exercises (name its id) do you predict would misbehave first if given a much larger input than its hidden tests use, and name the specific mechanism (recursion depth, exponential call-tree growth, or a hidden O(n) operation inside a loop), not just "it would be slow."

Deliverable and self-check. One short write-up containing: both working implementations, the small hand-verified agreement check, your written prediction (dated before you measured, not adjusted afterward), the full timing table across both markets and all four sizes, your Big-O classification argued from the shape of the data (not merely asserted), and the reflection naming a specific code-pack exercise and mechanism. Score yourself 2 points each for: (a) both implementations are correct and agree on the small check; (b) all sixteen timings (2 implementations × 4 sizes × 2 markets) are present; (c) the prediction was genuinely written before the measurements, not reverse-engineered afterward; (d) the Big-O classification is argued from the observed growth shape, with numbers, not just stated; (e) the reflection names a real code-pack exercise id and the correct specific mechanism. Pass at 8/10, with no zero on any item.

Code Lab: open the CS1.04 code pack in the Practice tab: eight exercises, CS1.04-e01 through CS1.04-e08, covering recursion mechanics, the mutable-default-argument trap, memoization, empirical Big-O measurement, recursive and iterative divide-and-conquer, the recursion-depth limit, nested-loop reduction, and a classic exponential divide-and-conquer puzzle, and clear every one of its hidden tests, not merely the single visible example shown for each.

Reading & resources

Everything below is an anchor to build intuition from and verify your own reasoning against, never a substitute for deriving a complexity class yourself by counting. Free unless marked; level tags run from intuition to full rigor.

Building the intuition (read these first):

Aditya Y. Bhargava, Grokking Algorithms: the friendliest fully-illustrated treatment of Big-O and recursion; the source of much of this module's "trace it by hand" ethos. [$ Paid] [Beginner]
Real Python, "Thinking Recursively in Python", a clear, code-forward tutorial covering base cases, recursive cases, and Python-specific gotchas (including the recursion limit). [Free] [Beginner]
Big-O Cheat Sheet (bigocheatsheet.com), a fast visual reference for the complexity ladder and the common-operation complexities of built-in structures. [Free] [Beginner–Intermediate]

Going deeper (for when you want full rigor):

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms (universally "CLRS"), the canonical, rigorous reference for asymptotic notation, recurrences, and divide-and-conquer proofs; not required to finish this module, essential if you want the full mathematical treatment later. [$ Paid] [Advanced]
MIT OpenCourseWare, 6.006 Introduction to Algorithms (lecture videos and notes), a full university-grade treatment covering everything in this module and the whole of CS1.05 beyond it. [Free] [Intermediate–Advanced]

Official, perishable references:

The Python documentation for sys.getrecursionlimit() / sys.setrecursionlimit(), the authoritative, current statement of your interpreter's actual recursion ceiling; this module's "1,000" is this Python release's default, not a permanent constant of the language. [Free] [Beginner] (as of 2026-07: check against your own interpreter)
The Python documentation for the timeit module, the standard-library tool for rigorous micro-benchmarking, a more careful cousin of this module's minimal time_it harness for when you need statistically robust timing. [Free] [Beginner–Intermediate]

Do this, not just read: open a Python shell, run import sys; print(sys.getrecursionlimit()), and confirm the number for yourself. Then paste this module's naive fib_naive into it and time fib_naive(30) and fib_naive(34) directly, watch the number of seconds roughly multiply by φ⁴ ≈ 6.85 between them, exactly as the identity in Worked Example 3 predicts, before you ever touch the memoized version. Ten minutes of watching a number you predicted on paper show up, unprompted, on your own machine will install this module's central habit faster than any amount of additional reading.

Teach it back & journal

Feynman prompt. Explain to a smart friend who has written a few working Python scripts but has never heard the phrase "Big-O" why their script that "worked great on my test file" might still fail badly on the real dataset next week, using the idea that tests on a small size prove correctness at that size, and prove nothing about how the cost changes as the size changes. Then, in the same breath, explain why a recursive function can be completely logically correct and still crash, using the idea that the call stack is real, finite memory, and a correct recursive definition can still run out of it. If your friend can, unprompted, look at a piece of code with a loop nested inside a loop and predict "that's going to get much worse as the data grows, not just a little worse", and say roughly how much worse, you have installed the mechanism this module exists to teach.

Journal prompt. For one working session, before running any piece of code you write or receive (including from an AI assistant), pause and write down, in one sentence, your prediction of its Big-O time complexity and whether its recursion depth (if any) is bounded by something small or by the size of the data. Then run it, and where possible, time it at a couple of different input sizes. Log what happens: How many of your predictions were right? Which ones were wrong, and what did you miss when you first read the code, a hidden operation inside a loop, an unbounded recursion depth, a base case you assumed was reachable but wasn't? Then write a paragraph on this: the difference between a programmer and an analyst who codes is not who writes more code faster, a copilot can help either one type faster, it is who can look at a piece of code, before running it, and say what it will cost when the data is not the size it is today. Which single habit from this module, counting operations before guessing, tracing the base case's reachability, or profiling across genuinely different sizes rather than trusting one test, would most change how a reviewer sees the quality of your code, and what will you do this week to make it automatic?

This module's flashcards and mastery quiz are wired into the app: see the node's Quiz and Reviews.

Algorithmic Thinking, Recursion & Big-O