—

Artificial Computational Intelligence

Analyzing Recursive Algorithms

Published: 2026-08-09

Level: postgraduate

Audience: Postgraduate students learning to analyze recursive algorithms

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

The basic operation and the general analysis plan — covered in Lecture 1 (The Basic Operation Method)
Primitive operations and the RAM model — covered in Lecture 1 (The RAM Model and Primitive Operations)
Running time and time efficiency — covered in Lecture 1 (Efficiency: Space and Time)

The previous session covered the running time of ordinary algorithms with no recursive calls. This session turns to recursive algorithms: what they are, how to write their running time as a recurrence, and how to solve that recurrence with the iterative method, the recursion tree method, and the master method.

The road map for this session: first, what recursion is and why the base case exists (3.1). Then a first worked example — recursive maximum (3.2) — which gives us something concrete to analyze. From that example we extract the idea of a recurrence equation and learn the iterative method for solving it (3.3). A general five-step plan for analyzing any recursive algorithm follows, together with the shift from primitive operations to the single basic operation (3.4). That plan is applied to factorial (3.5), Tower of Hanoi (3.6), and counting binary digits (3.7). Then two faster solution methods: the recursion tree method (3.9) and the master method (3.10), with a note on why the substitution method is deferred (3.8). The session closes with exam guidance and the industry view of what these running times mean in practice.

3.1 Recursion and the Base Case

3.1.1 What Recursion Really Means

Hook: How can a procedure that calls itself ever finish? It cannot — unless every self-call is aimed at a smaller version of the same task. That shrinking is the whole secret of recursion.

A recursion is a procedure P calling itself. Almost everyone knows that much. The second half is the part almost everyone ignores: every call to P exists to solve a sub-problem of smaller size. When we call the same procedure P again, we are not solving the same problem again — the input size has shrunk. That shrinking is the catch, and it is also the property we exploit when we analyze the algorithm.

Intuition + analogy: Think of Russian nesting dolls. Every doll contains a smaller copy of itself; the chain of smaller copies cannot go on forever — it bottoms out at the tiniest solid doll, which contains nothing. A recursive call is the same: each call opens a smaller copy of the problem, and the copies keep shrinking until one of them is small enough to answer directly without any further copies. The analogy breaks in one place: a nesting doll only contains smaller dolls, while a recursive call returns an answer back up the chain — the inner calls hand their results to the calls that opened them.

Why does the size need to shrink? If every call solved a problem of the same size, the calls would never make progress toward an answer. The shrinking is what eventually lets the chain of calls reach a stopping point. Keep this in mind for every recursive algorithm: the calls form a chain of smaller and smaller versions of the original problem, and each version feeds the next.

Formalize — the two-part structure of every recursive procedure: A recursive procedure P is defined by exactly two kinds of rules:

The recursive rule (otherwise case): for inputs above some threshold, P's definition contains a call to P itself on a strictly smaller input. The smaller size is what guarantees progress: after enough applications of the rule, the input must fall below the threshold.
The direct rule (base case): for inputs at or below the threshold, P is answered directly — no call to itself appears anywhere in that branch.

The textbook treatment of divide-and-conquer states the same structure in three steps applied at every level of recursion: divide the problem into smaller instances of itself, conquer by solving them recursively (and solve directly once they are small enough), and combine the sub-solutions into the full answer. Recursive maximum, factorial, Tower of Hanoi, and binary-digit counting in this session are all instances of this pattern: one rule that recurses on a smaller size, and one rule that answers the smallest case outright.

3.1.2 The Base Case

A base case is the smallest unit of a recursive algorithm that can be solved directly, without using recursion. If every call needed another recursive call, the procedure would keep running forever. The base case is what stops it.

So a recursive procedure should always define a base case, and that base case must be small enough to be solved directly. Whenever you hear "base case," this is what it means: the smallest instance, answered directly, with no recursion involved. Every recursive algorithm needs two parts — the base case and the otherwise case — and a correct recurrence for it will have both as well.

Assumptions & scope: The base case must be reachable. That means two things must both hold: (1) the recursive rule must reduce the size by a strictly positive amount on every application, and (2) the base case must sit at the bottom of that chain of sizes. If the recursive rule halves the input, then the input sizes are $n, n /2, n /4, \dots$ — the base case must live at some size in that chain (typically 1), or the recursion will skip past it. If a rule reduces $n$ to $n - 1$ but the base case tests $n = 0$ , the chain $n, n - 1, \dots, 0$ still reaches it, so that is fine. What fails is a base case sitting above the shrinkage pattern — e.g., a rule that reduces $n$ to $n /2$ paired with a base case at $n = 3$ would miss 3 forever and never stop. Also note: the exact number at which the base case triggers (1, 2, or 100) does not matter for the asymptotic running time, only that it is a constant size solved directly — a point the professor returns to with $T (1)$ in the recursion-tree discussion.

Visual intuition: Picture a chain of boxes labeled with decreasing sizes — $n, n - 1, n - 2, \dots, 1$ . Each box points to the next smaller box (that is the recursive call), and the box labeled 1 is drawn solid: it points to nothing, because it holds the direct answer. The chain is the recursion; the solid box is the base case. The takeaway: a correct recursion is a chain that always ends in a solid box.

Pitfalls:

Forgetting the base case entirely — the classic infinite recursion. Every call creates a new call of the same size, so the chain never ends; in a real program the machine eventually runs out of memory on the call stack, but conceptually it "keeps running forever."
Calling the same size instead of a smaller size — e.g., a procedure that calls itself with $n$ instead of $n - 1$ . Even with a base case in the code, this branch never reaches it.
Confusing "base case" with "basic operation." These are different ideas: the base case is the smallest instance answered directly; the basic operation is the statement that executes the most times inside the recursion. The professor will later warn that writing "base operation" (mixing the two) is cut to zero on the exam.
Treating the base case's cost as the whole story — the base case is also a term in the recurrence equation (its constant time), so a correct recurrence has a base-case line and an otherwise line.

Recap + bridge: Recursion is a procedure calling itself on strictly smaller sub-problems, and the base case is the smallest instance that is answered directly — together they guarantee the call chain eventually stops. The next section makes this concrete: a recursive maximum-finding procedure is traced by hand, so you can watch the chain expand down to the base case and then unwind back up with answers.

Real-world connection: recursion is the mechanism behind the divide-and-conquer algorithms that run much of modern computing — merge sort (which sorts the arrays in a database engine), binary search (which finds a record in a sorted index in $O (lo g n)$ time), and recursive tree traversals (which walk file systems and parse expressions in compilers). In every one of them the same two-part contract appears: shrink the input, and answer the smallest case directly. Recursion is also how self-similar data is handled naturally — think of a folder tree inside a filesystem, where every folder is a smaller version of the whole tree: an engineer analyzing the time a filesystem crawler takes writes a recurrence, exactly as this session will now do.

3.2 Recursive Maximum: The First Worked Example

3.2.1 The Algorithm

Hook: You already know how to find the maximum of an array with a loop — so why study a recursive version that does the same job? Because it is the simplest possible case where a procedure calls itself, and the way its calls shrink lets us see — in full, on paper — everything that goes on inside a recursive algorithm. Every recursive running-time analysis in this session builds on this picture.

The recursive algorithm for finding the maximum element is introduced as a contrast to the ordinary version seen in earlier sessions. Input: an array a storing $n \geq 1$ integers. Output: the maximum element in a.

recursiveMax(a, n):
    if n = 1:
        return a[0]
    else:
        return max( recursiveMax(a, n - 1), a[n - 1] )

Formalize — reading the procedure line by line:

Parameters: the call comes with two arguments — the array a and the size n. The size is the parameter that shrinks; the array is passed along unchanged so every call works on the same data.
Base case (line 2–3): if only one element remains ( $n = 1$ ), that element is $a [0]$ , and it is by definition the maximum of a one-element array. Answer directly; no recursion.
Recursive case (line 5): the maximum of the first $n$ elements is computed as

$max (max of the first n - 1 elements recursiveMax (a, n - 1), the last element a [n - 1])$ The reasoning: the maximum of the whole array is the maximum of "the maximum of the first $n - 1$ elements" and "the last element." Whatever the biggest element of the first $n - 1$ is, comparing it against the final element either keeps it or replaces it — in both cases we get the true maximum of all $n$ elements.

Shrinking check (the recursion contract from 3.1): the recursive call uses size $n - 1 < n$ , and the base case sits exactly at the bottom of the chain $n, n - 1, \dots, 1$ . So the calls must eventually stop.

3.2.2 The Trace, Step by Step

Worked example — trace on a real array. Work it with a concrete array: $n = 5$ and $a = [4, 3, 2, 5, 1]$ , so $a [0] = 4, a [1] = 3, a [2] = 2, a [3] = 5, a [4] = 1$ .

Phase 1 — expand the calls downward (toward the base case):

Call recursiveMax(a, 5). Is $n = 1$ ? No. Return $max (recursiveMax (a, 4), a [4])$ , and $a [4] = 1$ . The call recursiveMax(a, 4) is not yet evaluated — it will be computed first.
That call expands: recursiveMax(a, 4) also has $n \neq = 1$ , so it returns $max (recursiveMax (a, 3), a [3])$ , and $a [3] = 5$ .
recursiveMax(a, 3) returns $max (recursiveMax (a, 2), a [2])$ , and $a [2] = 2$ .
recursiveMax(a, 2) returns $max (recursiveMax (a, 1), a [1])$ , and $a [1] = 3$ .
recursiveMax(a, 1): now $n = 1$ , so it returns $a [0] = 4$ . This is the base case; no further recursion.

The chain has reached the bottom. Note what has accumulated: a stack of pending max comparisons, each waiting for the value of the call below it.

Phase 2 — unwind the chain upward (with concrete values):

The deepest call returned 4 (recursiveMax(a, 1) = a[0] = 4). Plug it into the call from step 4: $max (4, 3) = 4$ , returned to the previous call;
$max (4, 2) = 4$ , returned up again;
$max (4, 5) = 5$ , returned up again;
$max (5, 1) = 5$ — the final answer.

Answer: the maximum of $[4, 3, 2, 5, 1]$ is 5.

Sense-check: 5 really is the largest entry of the array (the other entries are 4, 3, 2, and 1), and the recursion reported exactly 5 — the mechanics, not the numbers, did the work. Also note the honest price of the recursion: the answer 5 is reached only after the base-case value 4 travels back up through four comparisons. That chain of work is exactly what the recurrence equation of the next section will count.

The pattern holds for any recursive trace: expand the calls one by one until the base case is reached, then solve back, substituting values. Even if the idea does not click on first reading, run it yourself once with a small array — the mechanics are simple.

Visual intuition: Draw the five calls as a vertical stack of boxes — recursiveMax(a,5) on top, then (a,4), (a,3), (a,2), and the solid-boxed recursiveMax(a,1) at the bottom (the base case). Each box carries the one extra element it will compare against the answer coming up from below: 1, 5, 2, 3, and 4 at the base. The arrows point down while expanding, then flip upward while returning values. The takeaway: recursion builds a stack, and the base case supplies the first value that stack processes.

Pitfalls:

Thinking each call "recomputes the whole problem." recursiveMax(a, n-1) does not re-scan the array from scratch — it solves the smaller problem "max of the first $n - 1$ elements," and each level adds exactly one new comparison. The total work is a chain of $n - 1$ comparisons, not $n!$ of them.
Evaluating the max too early. When step 1 writes "return max(recursiveMax(a,4), a[4])", the value of recursiveMax(a,4) is unknown — you must descend first, then come back. Beginners who "substitute 4 and 1" immediately mis-trace.
Missing the base case's role in the value flow. The number 4 that starts the unwinding comes from the base case. If the base case returned something wrong (say $a [n - 1]$ instead of $a [0]$ ), every answer above it would be wrong too — one bug at the bottom poisons the whole chain.
Ignoring the recursion contract. If someone "optimized" this procedure by calling recursiveMax(a, n) (same size), it would never end. Every recursive call must move toward the base case.

Recap + bridge: The recursive maximum computes the maximum of $n$ elements as the maximum of "the maximum of the first $n - 1$ elements" and the last element — the calls expand down to the base case $n = 1$ , which returns $a [0]$ , and the chain unwinds back up with the answer. The next section asks the natural follow-up question: how many primitive operations does this whole chain of calls cost? That question is answered by writing the algorithm's running time as a recurrence equation.

Real-world connection: this exact pattern — "combine the answer for the rest of the data with the current element" — is the shape of recursive reduce operations used in distributed data processing (for example, computing the max, sum, or count over millions of records in a map-reduce-style pipeline). A single machine cannot hold all records, so the problem is cut into smaller parts, each part is reduced to a small answer, and the small answers are combined upward — precisely the expansion-then-unwind flow traced above, scaled to a cluster of machines.

3.3 Recurrence Equations and the Iterative Method

3.3.1 What a Recurrence Is

Hook: For a loop-based algorithm you can count iterations directly. But a recursive algorithm's running time is defined in terms of its own running time on smaller inputs — how do you solve an equation that contains the thing you are solving for? The answer is the subject of this whole section: write the self-referential description, then unwind it until the unknown disappears.

A recurrence is an equation or inequality that describes a function in terms of its values on smaller inputs. That fits recursive calls perfectly: the running time of a recursive algorithm satisfies such statements, and those statements are called a recurrence equation.

Formalize — the notation:

$T (n)$ is the running time of the algorithm on an input of size $n$ — the same notation used in the previous session for ordinary algorithms. The letter $T$ is a free choice; any letter works (this session later uses $M$ and $A$ for different algorithms). $T$ is used because time starts with T.
A recurrence equation is a two-line description: one line for the base case (small $n$ , solved directly, costing a constant) and one line for the recursive case (larger $n$ , expressed through $T$ of smaller sizes plus the extra work done at this level).
The phrase "in terms of its values on smaller inputs" is what makes a recurrence different from an ordinary equation: the unknown function appears on the right-hand side, evaluated at smaller arguments. That self-referential form is exactly the shape of the recursive call itself — a recurrence is the running-time mirror of the algorithm that produces it.

Recurrence definition (standard form): reference treatments state the same idea verbatim: a recurrence is an equation or inequality that describes a function in terms of its value on smaller inputs. The merge-sort recurrence $T (n) = 2 T (n /2) + Θ (n)$ with base case $T (1) = Θ (1)$ is the canonical textbook example of the form — two cases, recursive term first, extra work added at each level.

3.3.2 Writing the Recurrence for Recursive Maximum

A recursive algorithm must have two cases, and so must its recurrence: the base case and the otherwise case.

Base case, $n = 1$ : $T (1) = 3$ . Where does the 3 come from? Count the primitive operations performed when $n = 1$ : the comparison $n == 1$ (one operation), the return statement (one operation), and the array indexing $a [0]$ (one operation). That makes 3. The exact value is not important — the point is that the base case takes constant time.

Otherwise: $T (n) = T (n - 1) + 7$ . The $T (n - 1)$ is the time spent inside the recursive call on an input of size $n - 1$ . The $+ 7$ stands for everything else in the recursive part: one return statement, one max calculation, one recursive call, and the array indexing $a [n - 1]$ — four primitive operations — plus the three operations of the base case, because the recursive call eventually ends in the base case: $4 + 3 = 7$ .

Put together, the recurrence for recursive maximum is:

$T (n) = {3 T (n - 1) + 7 if n = 1 if n > 1$

For this first algorithm the primitive counting is done in full to show the minute details. From the next algorithm onward, primitive counting is abandoned.

Q: How does that 7 come about? Counting primitive operations in the recursive part gives only 4: one return, one max calculation, one recursive call, and one array indexing.

A: The recursive call also ends in the base case, so the 3 operations of the base case are added on top: $4 + 3 = 7$ . Whenever the recursion runs, the base condition still executes at the end of the chain, so its cost is included in the recursive call rather than counted separately. But there is no need for this micro detail going forward — only the fact that it is a constant matters.

3.3.3 Solving the Recurrence with the Iterative Method

The goal is a closed form: a version of the equation with no reference to the function $T$ on the right-hand side. With $T$ on both sides, we cannot solve for $T$ yet.

Intuition + analogy: Think of a maintenance budget for a chain of $n$ workstations. Every workstation costs 7 rupees to service and then passes the job to the next workstation, which is one step closer to the end of the chain; the last workstation is the base case, costing 3. The total bill is "3 for the last one, plus 7 for each of the $n - 1$ service stops" — but to prove that, you cannot just assert it: you unwind the chain one station at a time and watch the pattern emerge. That unwinding is the iterative method.

Worked example — the iterative method in full. Start from the recurrence:

$T (n) = T (n - 1) + 7$

Express $T (n - 1)$ using the same recurrence with $n$ replaced by $n - 1$ :

$T (n - 1) = T (n - 2) + 7$

Substitute that back in:

$T (n) = T (n - 2) + 7 + 7 = T (n - 2) + 2 \cdot 7$

Repeat once more:

$T (n) = T (n - 3) + 3 \cdot 7$

$T (n) = T (n - 4) + 4 \cdot 7$

These are mere substitutions, nothing more. After $i$ substitutions the general form is:

$T (n) = T (n - i) + 7 i$

The general form still has $T$ on the right, so it is not yet closed. Which value of $i$ turns the right-hand side into a case we know? The base case is $T (1) = 3$ , so we want $n - i = 1$ , meaning $i = n - 1$ . (If we had set $i = n$ , we would get $T (0)$ — and we do not know $T (0)$ , so there would be nothing to substitute.) This is the thought process behind choosing $i$ : use the information you actually know. Substituting $i = n - 1$ and the known base value:

$T (n) = T (1) + 7 (n - 1) = 3 + 7 n - 7 = 7 n - 4$

So $T (n) = 7 n - 4$ .

Numerical sense-check: try $n = 5$ . The formula gives $7 \cdot 5 - 4 = 31$ . Directly from the recurrence: $T (1) = 3$ , then $T (2) = 3 + 7 = 10$ , $T (3) = 17$ , $T (4) = 24$ , $T (5) = 31$ . Both routes agree.

Now express it asymptotically. Since $7 n - 4 < 7 n$ , the value is bounded above by $7 n$ , and constants are dropped:

$T (n) = O (n)$

Q: Why big-O and not big-Omega or big-Theta when the exact value is $7 n - 4$ ?

A: $7 n - 4$ is less than $7 n$ , so $7 n$ is an asymptotic upper bound, and big-O is the upper-bound notation. We are not worried about the constant, so $7 n$ is simply $O (n)$ . The negative constant is a hint: the value sits below a clean multiple of $n$ , so an upper bound is the natural statement.

Assumptions & scope: The recurrence assumes $n$ is a whole number with $n \geq 1$ , and the base case costs a constant (here counted as 3). The exact constants (3 and 7) are an artifact of the primitive-operation bookkeeping convention — another convention might count a comparison as 2 or an assignment as 1 and get different numbers. That is fine and expected: the constants only matter here for pedagogy. What must survive every convention is the structure: a constant base case and a constant add-on per recursive level. Asymptotically, any constant base case and any constant add-on produce $T (n) = Θ (n)$ — linear growth. Changing $T (1)$ from 3 to 100 changes the exact solution but not the order of growth.

Visual intuition: Plot $T (n)$ against $n$ — horizontal axis: input size $n$ (units: elements of the array); vertical axis: $T (n)$ (units: primitive operations). The curve is a straight line starting at $T (1) = 3$ and rising with slope 7 — each added element adds exactly 7 operations. The landmarks: the y-intercept at $n = 1$ (base-case cost 3) and the slope (per-element cost 7). The takeaway: a recurrence of the form $T (n) = T (n - 1) + c$ always draws a line — one recursive call of size $n - 1$ means every input size adds the same constant, so the total is proportional to $n$ .

Pitfalls:

Choosing the wrong stopping point. The general form $T (n) = T (n - i) + 7 i$ must be closed using the base case you actually know. If you substitute $i = n$ you reach $T (0)$ , which the recurrence never defined — the derivation then dead-ends. Always ask: which value of $i$ lands on a known base case?
Stopping too early. Reaching $T (n) = T (n - 2) + 2 \cdot 7$ is not the answer — it still contains $T$ on the right. The closed form is reached only when the right-hand side is fully known.
Confusing the meaning of $T (n - 1)$ . $T (n - 1)$ is the total running time of the whole smaller call — everything inside it — not "one step." Adding +7 on top of it is correct because the +7 is the work of the current level only.
Dropping the negative constant sloppily. $7 n - 4$ being "less than $7 n$ " is precisely the justification for big-O. Saying "7n − 4, so Theta(n)" would need a matching lower bound (here $7 n - 4 \geq 6 n$ for $n \geq 4$ would work), but the lecture's choice of the upper-bound statement is the safer, cleaner one.

Exam note: Time calculations of exactly this kind — counting the base case, writing the recurrence, solving it — will be asked in the quiz. The quiz comes after session four; this is the drill the professor stressed more than once.

Recap + bridge: A recurrence describes the running time of a recursive algorithm through its own values on smaller inputs — two lines, a base case and a recursive case; the iterative method unwinds the recursive case by repeated substitution until a pattern appears, then closes the pattern at the known base case, giving $T (n) = 7 n - 4 = O (n)$ . Before the next example, the lecture steps back and lays out the general five-step plan for analyzing any recursive algorithm — and replaces primitive-operation counting with the single basic operation.

Real-world connection: when an engineer profiles a slow program and finds a function that keeps calling itself once per input element, the recurrence $T (n) = T (n - 1) + c$ is the tool that predicts the problem: double the input, double the time, because the plot is a straight line. The same analysis, with $T (n) = T (n - 1) + c$ , tells you that a naive recursion that strips one element per call (like this maximum-finder, or a recursive string reversal) scales linearly — fine for a few thousand records, and exactly the reasoning a database or web-service engineer uses before choosing a loop, a recursion, or a divide-and-conquer split.

3.4 The General Plan and the Shift to Basic Operations

3.4.1 The Five-Step Plan

Hook: Every recursive algorithm in this course — and on the quiz — is analyzed by the same five moves. Learn the moves once, and each new algorithm is just a new set of numbers inside the same skeleton.

Before the next example, the general plan for analyzing any recursive algorithm:

The five-step plan (procedure):

Identify the parameter to be considered, based on the size of the input. For us that parameter is $n$ . Everything later refers back to this choice: the base case tests it, the recurrence decreases it, and the final answer is a function of it.
Get the number of times a basic operation is executed. The basic operation is the statement that dominates the running time (defined precisely in 3.4.2); we count how many times it runs, not how many times every statement runs.
Get the initial condition — the base case. The smallest instance, where the basic operation count is known directly.
Get a recurrence relation. Assemble the previous two ingredients into the two-line equation: the base case line plus the recursive-case line.
Solve the recurrence relation, get the order of growth, and express it in asymptotic notation. Use the iterative method (3.3), the recursion tree method (3.9), or the master method (3.10) to reach the closed form, then report it in $O$ , $Ω$ , or $Θ$ notation.

When this plan works and when it bends: The plan assumes the input is described by one size parameter $n$ , which is the standard setting for this course's algorithms. It extends naturally when a problem has two size parameters (e.g., an $m \times n$ matrix) — step 1 then picks the parameter that governs the recursion, and the final order of growth may involve both. The plan also assumes the basic operation is identifiable inside the recursion; for algorithms whose cost is dominated by the merge/combine step (like merge sort, where the comparisons are the basic operation), step 2 is still carried out in the recursive part — comparisons happen there — so the plan survives. What the plan does not do is tell you which of the three solving methods to use; steps 1–4 are mechanical, step 5 is where judgment enters.

3.4.2 Primitive Operations Are Out; Basic Operations Are In

The recursive-maximum analysis counted every primitive operation, for the sake of understanding the minute details. That method is now abandoned. From here on only the basic operation matters — the statement that contributes the most to the running time. Primitive operations are forgotten entirely; the basic operation alone decides the order of growth.

What counts, exactly: the basic operation (sometimes called the basic step in reference texts) is the statement that executes the maximum number of times and so dominates the running time. The idea matches the standard textbook practice of isolating one dominant cost — like comparisons in a sorting algorithm or multiplications here — and ignoring the rest. Every other statement's executions are at most a constant factor of the basic operation's count, so they cannot change the order of growth.

How do you find the basic operation in a recursive algorithm? Look in the recursive part, not the base case. In a recursive algorithm, recursion is what matters, so the basic operation is the one executing the maximum number of times inside the recursion. There is no thumb rule to apply blindly: just look at the algorithm, see which operation runs most often, and treat everything else as a constant.

Intuition + analogy: Measuring an algorithm by its basic operation is like estimating a highway trip by the time on the highway stretches and ignoring the few minutes of traffic lights at the ends: the lights are constant regardless of distance, so the trip's growth is decided entirely by the highway. The basic operation is the "highway" statement — it runs once per recursive level (or per iteration), so its count grows with $n$ ; the rest are "traffic lights" — a constant number per level, irrelevant at scale.

Visual intuition: Picture a horizontal bar for every statement in the algorithm, drawn to scale with its execution count on the horizontal axis. The bars for the base-case statements are stubby and flat — they do not grow with $n$ . The bar for the recursive-part statement is long and keeps growing as $n$ grows. The basic operation is the longest bar, and the total height of the stacked picture is dominated by it; the stubby bars are absorbed into the constant. One-sentence takeaway: in a recursive algorithm, the longest bar always lives inside the recursion.

Pitfalls:

Hunting in the base case. The base case runs once, so none of its statements can be the basic operation — it executes a constant number of times. Look inside the recursive part.
Counting everything "just to be safe." That was the primitive-operation approach, explicitly abandoned. Counting extra statements may change the constant but cannot change the order of growth — the point of the shift.
Inventing a thumb rule. There is none. Two recursive algorithms can have different basic operations (factorial's is multiplication; a recursive comparison-based search's is the comparison); the only reliable method is to read the algorithm and see which operation runs the most times.
Forgetting that the base case still exists. Dropping primitive counting does not drop the base-case line of the recurrence — the initial condition (plan step 3) still comes from the base case, but its value is now counted in basic operations only (often 0 or 1), not in every primitive.

Recap + bridge: The general plan is five moves — size parameter, basic-operation count, base case, recurrence, solve and state asymptotics — and the dominant cost to count is the single basic operation inside the recursive part. The next section applies this immediately: factorial's recurrence $T (n) = T (n - 1) + 1$ , whose basic operation is the multiplication.

Real-world connection: this is the same move every performance engineer makes when a profiler flags a function: find the single hottest line (the basic operation) and ignore the rest, because optimizing a line that runs once per call does nothing for the order of growth. When a service is slow, the question is never "how many statements run?" but "which statement runs once per element, and how many elements are there?" — exactly the two questions steps 2 and 1 answer.

3.5 Factorial: Basic Operations in Action

3.5.1 The Algorithm and Its Recurrence

Hook: You have multiplied $1 \cdot 2 \cdot 3 \dots n$ since school — but how many multiplications does the recursive version actually perform? Counting the answer with the new basic-operation rule is the first real application of the five-step plan.

The factorial function, known since elementary school, written recursively:

factorial(n):
    if n = 0:
        return 1
    else:
        return n * factorial(n - 1)

Step 1 of the plan — the size parameter is $n$ . Step 2 — the basic operation is multiplication. The recursive call factorial(n-1) is not an operation to count; the operation that contributes the most running time is the multiplication $n \times factorial (n - 1)$ . It sits in the recursive part (the rule from 3.4.2), and it runs exactly once per recursive call — no other statement in the algorithm is executed more often.

So the recurrence has two cases. Step 3 — the base case, $n = 0$ : when $n = 0$ , no multiplication happens at all — only a return of 1 — so $T (0) = 0$ . Step 4 — the recursive case:

$T (n) = T (n - 1) + 1$

The $T (n - 1)$ is the time to compute factorial(n-1), and the $+ 1$ is the one multiplication that finishes the job.

Worked example — counting the multiplications directly. Run factorial(4) by hand, marking each multiplication:

factorial(4) → 4 * factorial(3) — multiplication 1, call on 3.
factorial(3) → 3 * factorial(2) — multiplication 2, call on 2.
factorial(2) → 2 * factorial(1) — multiplication 3, call on 1.
factorial(1) → 1 * factorial(0) — multiplication 4, call on 0.
factorial(0) → returns 1 — no multiplication.

Then the values flow back: factorial(1) = 1·1 = 1, factorial(2) = 2·1 = 2, factorial(3) = 3·2 = 6, factorial(4) = 4·6 = 24.

Answer: $T (4) = 4$ multiplications — exactly $n$ . The recurrence predicted $T (n) = n$ , and the hand trace confirms: with $n = 4$ , four multiplications happened and the base case contributed zero. Sense-check: 24 is the correct value of $4!$ , and the multiplication count equals the number of recursive levels, so $T (n) = n$ for every $n \geq 1$ .

Q: What is the value of the base case? Some said 2, others said 1.

A: Using the basic-operation method it is 0: when $n = 0$ no multiplication is performed, only a return of 1. The wrong guesses drew a playful warning that in a live class the guessers would have had to hold their ears.

Q: Why is the return statement not the operation executing most?

A: Forget primitive operations completely. In recursive algorithms, check the recursive part for the basic operation, because recursion is what matters. The return statement lives in the base case; treat everything outside the recursive part as a constant.

3.5.2 Solving the Recurrence

Worked example — the iterative method. $T (n) = T (n - 1) + 1$ , so express $T (n - 1)$ the same way and substitute:

$T (n - 1) = T (n - 2) + 1$

$T (n) = T (n - 2) + 2$

Keep going to the general form:

$T (n) = i + T (n - i)$

The known base case is $T (0) = 0$ , so choose $i = n$ to bring $T (0)$ onto the right-hand side (unlike recursive maximum, whose base case sat at $n = 1$ and required $i = n - 1$ , here the base case is at $n = 0$ , so the full $n$ substitutions are needed):

$T (n) = n + T (0) = n$

Answer: $T (n)$ is exactly $n$ , so:

$T (n) = Θ (n)$

Sense-check: for $n = 4$ the formula gives $T (4) = 4$ , matching the hand trace above — the closed form reproduces the direct count.

Q: Shouldn't $n - 1$ also be counted along with the multiplication?

A: $T (n - 1)$ already stands for the time taken to solve the problem of size $n - 1$ — it includes everything that happens inside that call. The +1 is only the last multiplication, the one that combines $n$ with the result of the smaller call.

Q: How does the answer come out as theta of N?

A: Because $T (n)$ came out exactly $n$ . If it had been $n - 1$ , we would have written big-O; if the leftover term were asymptotically lower than $n$ , big-Omega. The +1 is just a constant — it could even be something like $lo g n$ , anything asymptotically lower than $n$ .

Assumptions & scope: The count $T (n) = n$ assumes multiplication costs the same regardless of the operands — the standard constant-cost assumption for the basic-operation model, and fine for order-of-growth analysis. If the numbers get huge (say $n = 1000$ , where $n!$ has 2568 digits), a real computer pays more for big-number multiplication, but that cost is a property of the arithmetic library, not of the recursion structure; the number of multiplications is still $n$ . Also note the base-case position matters for the closed form: factorial's base case at $n = 0$ gives exactly $T (n) = n$ ; recursive maximum's base case at $n = 1$ gave $T (n) = 7 n - 4$ . Same shape of recurrence, different constants and different base positions — and the same linear order of growth either way.

Visual intuition: Imagine a staircase with $n$ steps, one step per recursive level, and each step costing exactly one multiplication; the floor below the first step is the base case, costing 0. The total climbing cost is the number of steps — the staircase's height is $n$ . One-sentence takeaway: one recursive call of size $n - 1$ plus one unit of work draws a straight staircase, total height exactly $n$ , so $Θ (n)$ .

Pitfalls:

Guessing the base case from the return value. The base case returns 1, but its cost is 0 — no multiplication runs there. Cost and returned value are different things; students who answer "1" or "2" are pricing the value instead of the operations.
Counting the recursive call as a primitive operation. factorial(n-1) is not an operation with a cost of its own — its whole cost is $T (n - 1)$ by definition. Adding +1 for it would double-count.
Writing $Θ$ when the closed form is only an upper bound. Theta was correct here only because the solution is exactly $n$ . For a bound like " $2 n$ or less," big-O would be the honest notation.
Carrying primitive-operation habits into the base case. With the old method, the base case of factorial would have cost something like 1 (the return); with the basic-operation method it costs 0 because no multiplication runs. Both are constants — but the exam-relevant value under the new method is 0.

Recap + bridge: Factorial's basic operation is the multiplication in the recursive part; the recurrence $T (0) = 0$ , $T (n) = T (n - 1) + 1$ solves to exactly $T (n) = n$ , so $T (n) = Θ (n)$ — the first clean application of the five-step plan. The next algorithm is the classic Tower of Hanoi, whose recursion doubles the work at every level — and whose analysis introduces geometric progressions.

Real-world connection: the factorial count $n$ multiplications is the running time of a straightforward recursion; this is why real systems compute factorials iteratively, and why the number of combinations $(k n) = \frac{n !}{k ! ( n - k )!}$ — which appears in probability and statistics packages — is evaluated with tables or optimized routines rather than by direct factorial recursion: the recursion itself is linear, but the values explode. Counting the basic operation is how a systems engineer explains why a "trivial" recursion is or is not the bottleneck before writing it into a library.

3.6 Tower of Hanoi

3.6.1 The Problem

Hook: A puzzle with just three pegs and a handful of disks — how many moves does a complete solution need? The answer grows so fast that 64 disks would outlast the universe. Watching the number of moves explode is where this course first meets exponential time.

Tower of Hanoi is one of the classic complex problems. We have $n$ disks of different sizes and three pegs. Initially all disks sit on the first peg, stacked in order of size — the largest on the bottom, the smallest on the top. The goal is to move all disks to the third peg, using the second peg as an auxiliary when needed. Two rules govern every move: move only one disk at a time, and never place a larger disk on top of a smaller one — at any time.

3.6.2 The Recursive Algorithm

The recursive algorithm has only three steps:

hanoi(n, source, destination, temp):
    if n = 1:
        move the disk from source to destination
    else:
        hanoi(n - 1, source, temp, destination)   # move n-1 disks off the way
        move the nth disk from source to destination
        hanoi(n - 1, temp, destination, source)   # move n-1 disks onto the target

Reading the three steps:

Base case ( $n = 1$ ): a single disk moves straight from source to destination — one move, no recursion.
Step 1 — clear the way: move $n - 1$ disks from source to temp, using destination as an auxiliary peg — you move one disk at a time, and "somehow" you do it; that "somehow" is the recursive call hanoi(n-1, source, temp, destination). Why is this legal? The destination peg is the spare, so the largest disk can wait untouched on source.
Step 2 — the biggest disk: once those $n - 1$ disks are gone, the source holds only the nth (largest) disk, so move it straight from source to destination. The destination is empty or holds only bigger disks, so the rule "no larger on smaller" is respected.
Step 3 — rebuild the tower: move the $n - 1$ disks sitting on temp from temp to destination, using source as an auxiliary — the recursive call hanoi(n-1, temp, destination, source).

The two recursive calls both operate on size $n - 1$ , which is smaller than $n$ — the recursion contract from 3.1 holds, and the chain bottoms out at $n = 1$ . A short YouTube walkthrough (a link was shared) makes the sequence of moves much easier to follow than a written description.

3.6.3 Recurrence and Analysis

The time function here is called $M$ instead of $T$ — the letter is a free choice, and $M$ is the same idea as $T$ .

Base case: $M (1) = 1$ . With a single disk, one move takes it from source to destination — one basic operation (the basic operation here is a disk move).

Otherwise: the time to solve a problem of size $n$ equals the time to move $n - 1$ disks from source to temp, plus the time to move the nth disk, plus the time to move $n - 1$ disks from temp to destination:

$M (n) = 2 M (n - 1) + 1$

Two sub-problems of size $n - 1$ (so the $2 M (n - 1)$ ) and one extra move for the largest disk (the $+ 1$ ).

Worked example — the iterative method with the geometric progression. Now solve it by the iterative method. Expand $M (n - 1)$ using the same recurrence:

$M (n - 1) = 2 M (n - 2) + 1$

$M (n) = 2 (2 M (n - 2) + 1) + 1 = 4 M (n - 2) + 2 + 1$

One more step, and the coefficient doubles at every expansion:

$M (n) = 8 M (n - 3) + 4 + 2 + 1$

The pattern after $i$ expansions: the leading coefficient is $2^{i}$ , and the tail is the geometric progression $1 + 2 + 4 + \dots + 2^{i - 1}$ . The general form:

$M (n) = 2^{i} M (n - i) + (2^{i} - 1)$

The tail $1 + 2 + 4 + \dots + 2^{i - 1}$ is a geometric progression with first term 1 and common ratio 2. The sum of a GP with first term $a$ , common ratio $r$ , and $n$ terms is $a (r^{n} - 1) / (r - 1)$ , so the tail sums to $(2^{i} - 1) / (2 - 1) = 2^{i} - 1$ . (This is the standard geometric-summation result — in binary arithmetic it is the familiar fact that $1 + 2 + 4 + \dots + 2^{i - 1} = 2^{i} - 1$ , the largest integer representable with $i$ bits.) This is where geometric progressions enter the analysis — refresh GP formulas along with logarithms and arithmetic progressions.

The known base case is $M (1) = 1$ , so choose $i = n - 1$ :

$M (n) = 2^{n - 1} M (1) + 2^{n - 1} - 1 = 2^{n - 1} + 2^{n - 1} - 1 = 2^{n} - 1$

Answer:

$M (n) = 2^{n} - 1$

Numerical sense-check: for $n = 3$ , the formula gives $M (3) = 2^{3} - 1 = 7$ — and the classic puzzle with three disks is indeed solved in exactly 7 moves (small disk to temp, medium to destination, small onto medium, large to destination, small to temp, medium onto large, small onto large). The formula matches the puzzle's known answer.

Asymptotically:

$M (n) = O (2^{n})$

Q: Shouldn't that last 1 be dropped, since it is already in the base case when $n = 1$ ?

A: No. That 1 pays for the move of the nth disk from source to destination — the one move of the largest disk. It has nothing to do with the base case.

Q: Could the constant be 2, 3, or 4 instead of 1?

A: It does not matter. As long as the $2 M (n - 1)$ part is correct, the answer stays $2^{n}$ . Constants do not matter much — you will see this again as you do more exercises.

Assumptions & scope: The recurrence $M (n) = 2 M (n - 1) + 1$ holds for any $n \geq 2$ with a single move of the largest disk per level — the "+1" is structural, not a counting convention: it is one disk move, genuinely performed. Note what the solution $2^{n} - 1$ does not assume: no powers-of-two assumption, no divisibility — $n$ can be any whole number, because the size shrinks by exactly 1 per level. (Contrast this with the halving recurrences of 3.7 and 3.9, which need the power-of-two trick.) Also, $O (2^{n})$ is the answer for the number of moves; the space used by the recursion is different — only $n$ stack frames, i.e., $O (n)$ memory — a fact worth keeping straight in interviews.

Visual intuition: Draw the recursion tree of hanoi(3, ...): the root is the single move of disk 3, its two children are the two recursive towers of size 2, each of those splits into two size-1 leaves — 1 + 2 + 4 = 7 nodes, one per actual disk move. Vertical axis: depth of recursion (levels 0, 1, 2); horizontal axis: the tree's leaves. The tree is perfectly balanced and every node is a real move; the total node count doubles at each level, which is the geometric series in action. One-sentence takeaway: when every problem spawns two sub-problems of size $n - 1$ , the tree's node count is a GP summing to $2^{n} - 1$ .

Pitfalls:

Dropping the "+1" as if it were a counting artifact. It is a real move — the largest disk travels exactly once. The recurrence without it ( $M (n) = 2 M (n - 1)$ ) would solve to $2^{n - 1}$ , wrong by a factor of 2 and inconsistent with the 7-move solution for $n = 3$ .
Forgetting the GP sum formula at the moment of need. The tail $1 + 2 + 4 + \dots + 2^{i - 1}$ must be recognized as a geometric progression; students who try to count it term by term lose the pattern. The GP formula $a (r^{n} - 1) / (r - 1)$ is explicitly refreshable material for this course.
Writing $Θ$ loosely. The professor writes $O (2^{n})$ . Since $M (n) = 2^{n} - 1$ is exact, $Θ (2^{n})$ is also true — but the upper-bound habit (big-O) is the safer default statement, as emphasized repeatedly in this lecture.
Treating exponential time as a code smell by default. The professor's point is the opposite: for problems whose nature is exponential (Hanoi), no faster algorithm exists, and the exponential algorithm is the right one. The error is choosing exponential when a linear algorithm does exist.

Exam note (playful warning from the professor): teachers tend to teach three plus two and then ask square roots and powers. This exercise is deliberately harder than the ones that came before — do it yourself rather than waiting for the worked version.

Recap + bridge: Tower of Hanoi's recurrence $M (1) = 1$ , $M (n) = 2 M (n - 1) + 1$ doubles the sub-problems at every level; the iterative method turns the tail into the geometric progression $1 + 2 + \dots + 2^{n - 2}$ , summing to $2^{n} - 1$ , so the algorithm is $O (2^{n})$ . Exponential time is the problem's own nature — accepted when no better algorithm exists, but a poor excuse when a linear one does. The next algorithm, counting binary digits, changes the recurrence's shape completely: the size halves each level, and solving that recurrence needs the power-of-two assumption and logarithms.

Real-world connection: the number $2^{n} - 1$ also shows up as the exact cost of a famous real system: the backup-tape or "disk tower" discipline in early mainframe operations (the recursive algorithm for moving the disks was used in practice for tape rotation schedules). More broadly, exponential blow-up is the reason engineers count operations before building: a feature that doubles work per input level cannot run on production data — the same arithmetic that says "64 disks need $2^{64} - 1$ moves" says "a doubling recursion over a million records is dead on arrival," and the analysis that proves it is exactly the recurrence solved here.

3.7 Counting Binary Digits

3.7.1 The Algorithm and Its Recurrence

Hook: How many bits does the number 1,000,000 need? Guessing is hard; halving is not. The recursion that counts binary digits halves the number at every step — and the number of halvings turns out to be a logarithm. This is the first recurrence where the input size shrinks by division, and it introduces the logarithms that reappear in every divide-and-conquer analysis.

Here is an algorithm to find the number of binary digits in the binary representation of a number $n$ . If $n = 1$ , it returns 1; otherwise it halves the number and adds one — every halving accounts for one binary digit.

countBinaryDigits(n):
    if n = 1:
        return 1
    else:
        return 1 + countBinaryDigits(n / 2)   # halve the number, add one digit

Formalize — what is being counted. The basic operation here is the halving — the division of the current number by 2 (the operation that executes the maximum number of times, sitting in the recursive part per the rule of 3.4). Let $A (n)$ count halvings. The recurrence is easy to write now:

$A (1) = 0$

$A (n) = A (n /2) + 1 for n > 1$

Why is $A (1) = 0$ and not something bigger? Because when $n = 1$ , no basic operation happens — there is nothing to count. The $+ 1$ in the recursive case is the one halving (read differently, the one binary digit added by halving).

Reconciling the algorithm's return value with the recurrence: the procedure returns the digit count — 1 at the base, and one more per halving — so its return value is $A (n) + 1$ : the number of halvings plus the final digit that survives at $n = 1$ . For example, $n = 8$ : halvings are $8 \to 4 \to 2 \to 1$ , so $A (8) = 3$ , and the algorithm returns $3 + 1 = 4$ — which matches $100 0_{2}$ having 4 binary digits. The recurrence $A (n) = A (n /2) + 1$ with $A (1) = 0$ is the standard count of halvings, and it is what the asymptotic analysis is built on.

3.7.2 The Power-of-Two Assumption

The recurrence divides by 2, and division is awkward in a closed form. The trick: assume $n$ is a power of two, say $n = 2^{k}$ , so the divisions disappear. Then:

$A (2^{k}) = A (2^{k - 1}) + 1$

$A (2^{k}) = A (2^{k - 2}) + 2$

General form:

$A (2^{k}) = A (2^{k - i}) + i$

Worked example — solving under the assumption. The known base case is $A (1) = 0$ , so choose $i = k$ — then $2^{(k - k)} = 2^{0} = 1$ — and:

$A (2^{k}) = A (1) + k = 0 + k = k$

Finally convert back: since $n = 2^{k}$ , we have $k = lo g_{2} n$ , so:

$A (n) = Θ (lo g n)$

Answer: the number of halvings is exactly $lo g_{2} n$ when $n$ is a power of two, so $A (n) = Θ (lo g n)$ .

Numerical sense-check: $n = 16$ : $A (16)$ should be $lo g_{2} 16 = 4$ . Directly: $16 \to 8 \to 4 \to 2 \to 1$ — four halvings. The recurrence agrees, and the algorithm returns $4 + 1 = 5$ digits — $1000 0_{2}$ has 5 bits. Sense-check: the halving chain is exactly as long as the exponent $k$ in $n = 2^{k}$ , because each halving divides the exponent by one: $2^{k} \to 2^{k - 1} \to \dots \to 2^{0} = 1$ .

Big-O works too; the answer is exactly $lo g_{2} n$ , so theta is justified. The assumption $n = 2^{k}$ was only a solving aid — the answer is stated back in terms of $n$ . The same trick applies to any recurrence that divides by 2, 4, or any fixed factor: assume the input is a power of the divisor, solve, then substitute $k = lo g$ of the base.

Assumptions & scope: The clean equality $A (n) = lo g_{2} n$ holds exactly for powers of two. For arbitrary $n$ , the halving chain ends at 1 after $⌊ lo g_{2} n ⌋$ halvings (e.g., $7 \to 3 \to 1$ is 2 halvings, and $⌊ lo g_{2} 7 ⌋ = 2$ ), and the digit count is $⌊ lo g_{2} n ⌋ + 1$ — the standard formula. The power-of-two assumption is legitimate precisely because it does not change the order of growth: whether $A (n)$ is $lo g_{2} n$ or $⌊ lo g_{2} n ⌋$ , the answer is still $Θ (lo g n)$ . This matches the standard textbook practice of analyzing recurrences on exact powers of $b$ (here $b = 2$ ) and asserting the bound carries over — floors and ceilings do not change the asymptotics. The same caveat applies to any recurrence dividing by a fixed factor $b$ : assume $n = b^{k}$ , solve, convert with $k = lo g_{b} n$ , and the order of growth survives for all $n$ .

Visual intuition: Picture the halving chain $n \to n /2 \to n /4 \to \dots \to 1$ as a staircase where each step cuts the current number in half. Plot $lo g_{2} n$ against $n$ (horizontal axis: the number $n$ ; vertical axis: halvings needed). The curve is a slow, ever-flattening climb — to double the number of halvings you must square $n$ . The landmark: every tenfold jump in $n$ adds only about 3.32 halvings. One-sentence takeaway: halving-based recursion grows logarithmically — doubling the input adds exactly one more level of work.

Pitfalls:

Counting the base case's return as work. $A (1) = 0$ because no halving happens at $n = 1$ — the return of 1 is a digit, not a basic operation. Mixing the returned value with the cost is the same confusion the professor flagged in factorial.
Forgetting to convert back from $k$ to $n$ . The closed form $A (2^{k}) = k$ is in terms of the exponent; the final answer must be restated as $A (n) = lo g_{2} n$ , i.e., $Θ (lo g n)$ . Leaving the answer as " $k$ " fails step 5 of the plan.
Forcing a power-of-two assumption where the recurrence does not halve. The trick works for division by 2, 4, or any fixed factor $b$ (assume $n = b^{k}$ , substitute $k = lo g_{b} n$ ); it is not a generic license for other shapes of recurrence.
Writing "base operation." The correct term is basic operation. The professor's warning is blunt and exam-relevant: "base operation" on the exam is cut and marked zero.

3.7.3 The Right Term: Basic Operation

While the class worked through the exercises, one student wrote "base operation." The correction is sharp, and it is exam-relevant:

Q: Is it "base operation"?

A: It is the basic operation. "Base case" and "basic operation" are different things, and the term matters: if you write "base operation" on the exam, it will be cut and marked zero. And again — there is no thumb rule: look at the algorithm, find the operation that executes the maximum number of times, and in a recursive algorithm check the recursive part.

Recap + bridge: Counting binary digits halves the number at every step; the recurrence $A (1) = 0$ , $A (n) = A (n /2) + 1$ is solved by assuming $n = 2^{k}$ , which turns the closed form into $A (2^{k}) = k$ , i.e., $A (n) = lo g_{2} n = Θ (lo g n)$ — and the correct term is basic operation, not "base operation." The next section steps back from individual algorithms to survey the solving methods available for recurrences — and explains why the substitution method is skipped for now.

Real-world connection: halving recursions are everywhere in computing — binary search on a sorted list, finding the height of a balanced tree, and the exponentiation-by-squaring used in cryptography all run in $Θ (lo g n)$ because each step discards half the input. This is why searching a database index with a billion rows takes about 30 comparisons ( $lo g_{2} 1 0^{9} \approx 30$ ) rather than a billion — the same halving arithmetic as counting binary digits, applied by engineers who need to know whether a lookup stays fast as data grows.

3.8 The Methods for Solving Recurrences

Hook: You have now solved recurrences three times — but each time by the same hand-cranked substitution drill. There are faster tools: a visual one (the recursion tree) and a near-instant one (the master method). This short section lays out the menu before the remaining examples.

There are several methods for solving recurrences: the iterative method (already used twice), the substitution method, and the recursion tree method. This session covers the iterative method and the recursion tree method; then comes the master method, the easiest of all.

The menu at a glance:

Iterative method (used in 3.3, 3.5, 3.6): substitute the recurrence into itself repeatedly until a pattern appears, then close the pattern at the known base case. Strengths: works on any shape of recurrence, and it is the tool when the size decreases by a constant ( $n - 1$ ). Weakness: the algebra grows tedious for halving recurrences.
Recursion tree method (3.9): draw the recurrence as a tree — each node is one sub-problem's cost — sum the cost level by level, and add the levels. Strengths: visual, and it explains why the master method works. This session's remaining worked examples use it.
Master method (3.10): a cookbook for recurrences of the form $T (n) = a T (n / b) + f (n)$ — compare $f (n)$ against $n^{l o g_{b} a}$ and read off the answer from one of three cases. Strengths: fastest of all; no tree drawing, no substitution algebra. Constraint: only for the divide-and-conquer form $a T (n / b) + f (n)$ .
Substitution method (skipped here — see 3.8.2): guess the answer, then prove the guess by induction. Powerful in advanced work, but it demands the guess up front.

3.8.2 Why the Substitution Method Is Skipped

The substitution method requires you to guess the time complexity first and then prove the guess. The problem: we do not even know what guess to make yet. The verdict is blunt — even if it were taught, it would not work at this stage — so the substitution method is skipped for now.

The reasoning is honest and practical: a method whose first step is "guess the answer" is unusable until you have built the intuition for what recurrences typically answer. That intuition comes from exactly the tools this session does teach — the iterative method's patterns and the recursion tree's picture. Reference texts describe the substitution method as a two-step dance (guess the bound, then verify by induction), and they freely admit the hard part is producing the guess — recursion trees are the standard trick for generating one. In this course, the guess-first method is deferred until the groundwork exists.

Recap + bridge: The methods for solving recurrences form a menu — iterative substitution (done twice), the recursion tree (next), and the master method (after that) — while the substitution method is deliberately skipped because it demands a guess we cannot yet make. The next section teaches the recursion tree: the visual method that will make the master method's three cases obvious.

Real-world connection: knowing which solving tool to reach for is itself a professional skill — engineers analyzing a divide-and-conquer routine reach straight for the master method, while a recursion that strips one element at a time (like a naive text-tokenizer) is unwound by iteration. Choosing the wrong tool wastes time; recognizing the recurrence's shape — constant shrink, halving, or divide-and-conquer — decides the tool, exactly as this menu does.

3.9 The Recursion Tree Method

3.9.1 The Idea of the Recursion Tree

Hook: The iterative method solved every recurrence so far, but each one needed fresh algebra. Is there a way to see the answer? Yes — draw the recurrence as a tree, where every node is one sub-problem's cost, and the total running time is just the sum of the whole tree.

In a recursion tree, each node represents the cost of a single sub-problem somewhere in the set of recursive function invocations. The term at the root represents the cost at the top level of recursion — the very first invocation.

Formalize — how a recursion tree is built. Take the recurrence $T (n) = 3 T (n /4) + c n^{2}$ . The $c n^{2}$ is the cost of the first invocation apart from the recursive calls — exactly the role the +1 multiplication played in factorial. After the root cost, what remains are the recursive calls: three sub-problems of size $n /4$ , so the root has three children, each labeled $T (n /4)$ . Each child expands by the same recurrence: $T (n /4)$ becomes $3 T (n /16) + c (n /4)^{2}$ , and so on down the tree. The recipe in one sentence: each node's non-recursive cost is written on the node, its recursive calls become its children, and the recurrence is fully drawn when the sizes hit the base case. Reference texts state the same idea: in a recursion tree, each node represents the cost of a single subproblem somewhere in the set of recursive function invocations; we sum the costs within each level of the tree, then sum the level totals to get the total cost of all levels.

Does the tree stop? Yes — the sub-problem size shrinks at every level: $n, n /4, n /16$ , and so on, so sooner or later the size reaches 1, the base case. How far from the root is that? It is the height of the tree, and we can compute it — that computation is the first real calculation of the method.

3.9.2 Worked Example: Three Subproblems of Size n/4

Read the recurrence in words: a problem of size $n$ is divided into three sub-problems of size $n /4$ , and in every recursive call some basic operations run $c n^{2}$ times.

Worked example — the recursion tree for $T (n) = 3 T (n /4) + c n^{2}$ .

Step 1 — nodes and sizes level by level. Number of nodes at each level: level 0 has 1 node ( $3^{0}$ ); level 1 has 3 nodes ( $3^{1}$ ); level 2 has 9 ( $3^{2}$ ); level 3 has 27 ( $3^{3}$ ); level $H$ has $3^{H}$ nodes.

Size of the sub-problem at each level: level 0 has size $n$ ; level 1 has size $n /4$ ; level 2 has size $n /16 = n / 4^{2}$ ; level 3 has size $n / 4^{3}$ ; level $H$ has size $n / 4^{H}$ .

Step 2 — the height. At height $H$ the size becomes 1, so:

$n / 4^{H} = 1 ⟹ n = 4^{H} ⟹ H = lo g_{4} n$

This is where the familiar height formula comes from — it is derived, not memorized, and it depends on the divisor. If the size shrank by 2 every level, the height would be $lo g_{2} n$ .

Step 3 — the leaves. Number of nodes at the last level:

$3^{H} = 3^{l o g_{4} n} = n^{l o g_{4} 3}$

by the logarithm rule $a^{l o g_{b} n} = n^{l o g_{b} a}$ . So the last level holds $n^{l o g_{4} 3}$ nodes, each costing 1 at the base case.

Step 4 — the cost at each level. The root costs $c n^{2}$ . Each level-1 node costs $c (n /4)^{2}$ , and there are three of them, so level 1 costs:

$3 \cdot c (n /4)^{2} = \frac{3}{16} c n^{2}$

Level 2 costs $(3/16)^{2} c n^{2}$ , and level $i$ costs $(3/16)^{i} c n^{2}$ .

Step 5 — total time as a geometric series. Total time is the sum of the costs over all levels:

$T (n) = c n^{2} + \frac{3}{16} c n^{2} + (\frac{3}{16})^{2} c n^{2} + \dots + n^{l o g_{4} 3}$

The geometric series has ratio $3/16 < 1$ , so the root term $c n^{2}$ dominates:

$T (n) = O (n^{2})$

Answer: $T (n) = O (n^{2})$ . The answer was visible from the start — the root carries $n^{2}$ , the higher term — but you still compute the sum to confirm it. The sum in closed form is $\frac{1}{1 - 3/16} c n^{2} = \frac{16}{13} c n^{2}$ for the geometric part, plus the leaf cost $n^{l o g_{4} 3} T (1)$ ; since $lo g_{4} 3 \approx 0.79 < 2$ , the leaf term is asymptotically below $n^{2}$ , and the $n^{2}$ term wins. Sense-check: the level costs shrink by a factor $3/16 < 1$ each level, so the total is at most a constant multiple of the root cost — exactly the signature of an $O (n^{2})$ answer.

Q: Where does $c n^{2}$ come from as the root cost?

A: It is the cost of the first invocation apart from the recursive calls — the same role the +1 multiplication played in factorial. The remaining costs are the three recursive calls $T (n /4)$ .

Q: Why not $n$ squared over 16 at the root?

A: That value does appear — one level down. Each level-1 child costs $c (n /4)^{2}$ , and the three children together sum to $(3/16) c n^{2}$ .

Q: Are we sure the tree ends?

A: Yes. The sub-problem size keeps shrinking — $n, n /4, n /16$ — so eventually the tree reaches the base case.

Q: How far from the root does the base case appear?

A: The height of the tree: the level at which the size reaches 1. The height comes out of the derivation — $n / 4^{H} = 1$ — not out of memorized formulas.

Q: How do we know the division is by 4? And what if the input size is not a multiple of 4?

A: The recurrence states it: a problem of size $n$ splits into sub-problems of size $n /4$ . For inputs that are not multiples of 4, the answer depends on the problem — that question gets handled when it comes up. (The standard practice, followed by the textbooks, is to ignore floors and ceilings: replacing $n /4$ by $⌊ n /4 ⌋$ or $⌈ n /4 ⌉$ does not change the asymptotic answer.)

Q: Will the exam ask for these big summations?

A: Understand the concepts first; exams are a later worry. The instructor does not like checking math skills in an algorithms exam.

3.9.3 Worked Example: Two Subproblems of Size n/2

Worked example — the recursion tree for $T (n) = 2 T (n /2) + n$ . The recurrence $T (n) = 2 T (n /2) + n$ appears when an algorithm splits a problem of size $n$ into two sub-problems of size $n /2$ and does $n$ work per invocation.

Step 1 — nodes and sizes. Root: cost $n$ . Two children, each of size $n /2$ . Each of those expands into two children of size $n /4$ — four nodes at level 2, and so on: level $i$ has $2^{i}$ nodes, each of size $n / 2^{i}$ .

Step 2 — the height. The size reaches 1 at level $H$ :

$n / 2^{H} = 1 ⟹ H = lo g_{2} n$

Nodes at the last level:

$2^{H} = 2^{l o g_{2} n} = n$

Step 3 — the level costs. Cost at each level: level 0 costs $n$ ; level 1 costs $2 \cdot (n /2) = n$ ; level 2 costs $4 \cdot (n /4) = n$ ; the last level costs $n$ as well. So every level costs $n$ , and there are $lo g_{2} n$ levels:

$T (n) = n lo g_{2} n = Θ (n lo g n)$

Answer: $T (n) = Θ (n lo g n)$ . This is the signature of merge-sort-like divide-and-conquer — the merge-sort recurrence $T (n) = 2 T (n /2) + Θ (n)$ has exactly this solution, $Θ (n l g n)$ . Sense-check: doubling $n$ adds one more level ( $lo g_{2} 2 n = lo g_{2} n + 1$ ) and doubles the per-level cost, so the total roughly doubles plus one level's worth — $n lo g n$ grows just slightly faster than linear, which is exactly what the formula says.

Q: Can we really say exactly $N lo g N$ ? $N$ is huge.

A: In this case the total is exactly $n lo g n$ , so theta is fine. In general, whenever bigger terms are around, write big-O of $N lo g N$ to be on the safer side — big-O also covers the equality case.

Q: Why not big-Omega here?

A: There is no clean answer; think about large values of $N$ and how we account for time. We can rarely pin a running time exactly — even at work, when running programs, we speak in approximations. It is always safer to give an upper bound: you would say "I might take ten minutes" rather than five when you might need seven. We only count the basic operation, so some slack always remains.

Q: Is $T (1)$ an assumption?

A: $T (1)$ just means constant time. It could be $T (100)$ or $T (1000)$ — because $N$ is a very large value approaching infinity, the base case is a constant that does not involve the algorithm's complexity; it is solved directly.

Q: Why is $N + N + \dots + N$ equal to $lo g N$ times $N$ ?

A: Because the tree has $lo g N$ levels — the height — so the cost $N$ is added once per level, $lo g N$ times.

Assumptions & scope: Both examples assume the input size is an exact power of the divisor (4 in the first tree, 2 in the second) so that every division stays whole — the standard, tolerable simplification in recurrence analysis; floors and ceilings do not change the order of growth. The tree method itself applies to any recurrence whose sub-problem sizes shrink by a fixed factor, and also to uneven splits (like $T (n) = T (n /3) + T (2 n /3) + c n$ in advanced texts) — there the tree is not full and the height is bounded by the slowest shrinking branch. What the method requires is the ability to sum the level costs; when the level costs form a geometric series with ratio $< 1$ the root dominates (first example), when the ratio is $1$ every level ties and the height decides (second example), and when the ratio is $> 1$ the leaves dominate — the three possibilities that the master method of the next section codifies.

Visual intuition: Draw the first tree as a triangle of nodes, one per level: the top node is a big square labeled $c n^{2}$ , the next row has three smaller squares labeled $c (n /4)^{2}$ each, then nine smaller still — the squares shrink by a factor of $3/16$ of the total row width, so the rows' total areas form the geometric series. Horizontal axis: the number of nodes per row (1, 3, 9, ...); vertical axis: the cost of each node (shrinking like $1/1 6^{i}$ ). The landmark: the root square is visibly bigger than all the rows below it combined. For the second tree, draw rows of squares where each row's total area equals the root's exactly — a "rectangle of height $n$ and width $lo g n$ ". One-sentence takeaway: who wins — root, leaves, or a tie — is decided by whether the per-level costs shrink, grow, or stay constant down the tree.

Pitfalls:

Forgetting that each level- $i$ node's cost shrinks too. A level- $i$ node in the first tree costs $c (n / 4^{i})^{2}$ , not $c n^{2}$ — multiplying the node count $3^{i}$ by the full $c n^{2}$ would wrongly give $(3/4)^{i}$ -style series and a wrong answer.
Miscounting the leaves. The leaves number $3^{H} = n^{l o g_{4} 3}$ , which is not $3 \cdot (n /4)$ or anything similar — the exponent must be read off the logarithm identity $a^{l o g_{b} n} = n^{l o g_{b} a}$ .
Stopping at "the root dominates." The professor's point stands: the answer may be visible from the start, but you still sum the series to confirm it — the exam question is the sum, and shortcuts that skip it cannot be trusted.
Using the tree for recurrences that do not divide. For $T (n) = T (n - 1) + 7$ the "tree" is a single chain — the tree method adds nothing there; pick the iterative method for constant-shrink recurrences and the tree (or master method) for division-shrink recurrences.

Recap + bridge: The recursion tree turns a recurrence into a picture: nodes are sub-problem costs, level totals are summed, and the answer is root-dominated (geometric ratio $< 1$ , $O (n^{2})$ here), leaf-dominated, or a tie across $lo g n$ equal levels ( $n lo g n$ here). The next section extracts a cookbook from exactly this picture — the master method, which answers $T (n) = a T (n / b) + f (n)$ by comparing $f (n)$ with $n^{l o g_{b} a}$ , the root cost against the leaf cost.

Real-world connection: the $n lo g n$ tree is the shape of every good sorting algorithm (merge sort, heap sort) and of the balanced divide-and-conquer routines in database sort-merge joins — which is why sorting a billion records costs about 30 billion comparisons, not a billion-squared. The first tree's "root dominates" outcome is the shape of quicksort's worst case avoided and of unbalanced recursive splits in distributed computation, where one heavy top-level merge swallows the whole budget. Engineers who see their recursion profile as a tree know instantly whether the top level, the middle levels, or the leaves are eating the time — the same three-way diagnosis the master method formalizes.

3.10 The Master Method

3.10.1 The General Form

Hook: After the recursion tree, solving recurrences is still a small ritual of drawing and summing. The master method replaces the whole ritual with three if-this-then-that rules — read the recurrence, compare two functions, write the answer. It is the tool working engineers actually use.

The master method applies to recurrences of the form:

$T (n) = a T (n / b) + f (n)$

Formalize — reading the form. Read in English: a problem of size $n$ is divided into $a$ sub-problems of size $n / b$ each, and the cost of the first invocation — the work done apart from the recursive calls — is $f (n)$ . The parameters must satisfy $a \geq 1$ (a problem must split into at least one sub-problem) and $b > 1$ (the sub-problem size must shrink).

Everything needed falls out of the recursion tree picture: the level costs are $f (n), a \cdot f (n / b), a^{2} \cdot f (n / b^{2})$ , and so on; the height of the tree is $lo g_{b} n$ ; and the number of leaf nodes is $n^{l o g_{b} a}$ .

Q: How do we read $T (n) = a T (n / b) + f (n)$ in English?

A: A problem of size $n$ is divided into $a$ sub-problems of size $n / b$ each, and the cost of the first invocation is $f (n)$ — some processing that runs for $f (n)$ time in each invocation.

The master method is the one to use all the time — it is the easiest, and there is no time to waste drawing trees or iterating. Why was it not taught first? Because its terms — $f (n)$ , $n^{l o g_{b} a}$ , $a$ and $b$ — would have meant nothing without the recursion tree background. Now they mean something.

3.10.2 The Three Cases

Case 1 — the leaves win: $f (n) = O (n^{l o g_{b} a - ε})$ for some $ε > 0$ . Here $f (n)$ grows polynomially slower than $n^{l o g_{b} a}$ , so the leaves dominate:

$T (n) = Θ (n^{l o g_{b} a})$

Case 2 — a tie, settled by a log factor: $f (n) = Θ (n^{l o g_{b} a})$ . The two functions grow at the same rate, so neither dominates; a log factor is added:

$T (n) = Θ (n^{l o g_{b} a} lo g n)$

Case 3 — the root wins: $f (n) = Ω (n^{l o g_{b} a + ε})$ for some $ε > 0$ . Here $f (n)$ grows polynomially faster, so the root dominates:

$T (n) = Θ (f (n))$

with one extra condition: the regularity condition $a \cdot f (n / b) \leq c \cdot f (n)$ must hold for some constant $c < 1$ . That check is required before writing the case-3 answer.

The concept behind all three cases: compare the cost at the root, $f (n)$ , with the cost at the leaves, $n^{l o g_{b} a}$ . Whichever is larger decides the solution. The catch: the comparison must be polynomial, not merely asymptotic — look at the highest power of $n$ , not just the growth rate. (This is why $n lo g n$ loses to $n^{2}$ in case 1 but is not "polynomially larger" than $n$ : its power of $n$ is only 1.)

3.10.3 Worked Examples

Example 1 — $T (n) = 2 T (n /2) + n$ . Here $a = 2$ , $b = 2$ , $f (n) = n$ . Compute $n^{l o g_{b} a}$ first:

$n^{l o g_{2} 2} = n$

$f (n)$ and $n^{l o g_{b} a}$ are both $n$ — equal. That is case 2:

$T (n) = Θ (n^{l o g_{2} 2} lo g n) = Θ (n lo g n)$

Answer: $T (n) = Θ (n lo g n)$ . Same answer the recursion tree gave, in a fraction of the steps — and the theta is now fully justified, which clears the earlier big-O-versus-theta doubt. Sense-check: the recurrence $2 T (n /2) + n$ is merge sort's recurrence, whose known answer is $Θ (n lo g n)$ — the master method reproduces it instantly.

Example 2 — $T (n) = 9 T (n /3) + n$ . Here $a = 9$ , $b = 3$ , $f (n) = n$ :

$n^{l o g_{3} 9} = n^{2}$

because $3^{2} = 9$ — $n$ squared is larger than $n$ . Since $n^{2}$ is larger than $n$ , $f (n)$ grows polynomially slower than $n^{l o g_{b} a}$ — case 1:

$T (n) = Θ (n^{2})$

Answer: $T (n) = Θ (n^{2})$ . Sense-check: nine sub-problems of size $n /3$ with linear combine-work: the sub-problems alone produce $n^{2}$ -sized work at the leaves ( $9^{l o g_{3} n} = n^{2}$ leaves), so a quadratic answer is exactly what the tree picture predicts.

Example 3 — $T (n) = 3 T (n /4) + n lo g n$ . Here $a = 3$ , $b = 4$ , $f (n) = n lo g n$ . We need $lo g_{4} 3$ , and we do not need its exact value — only that $lo g_{4} 3 < 1$ (4 to what power gives 3? Less than $4^{1}$ , so less than 1). So $n^{l o g_{4} 3}$ grows more slowly than $n lo g n$ — case 3. Check the regularity condition:

$3 \cdot f (n /4) \leq c \cdot f (n) for some c < 1$

$3 \cdot \frac{n}{4} lo g \frac{n}{4} \leq c \cdot n lo g n$

holds for a suitable $c < 1$ , so:

$T (n) = Θ (n lo g n)$

Answer: $T (n) = Θ (n lo g n)$ . Sense-check of the regularity check: with $c = 3/4$ , the left side $3 \cdot \frac{n}{4} lo g \frac{n}{4}$ is less than $\frac{3}{4} \cdot n lo g n$ (since $lo g (n /4) < lo g n$ ), so the condition holds — and the tree's level costs are a geometric series with ratio $3/4 < 1$ , so the root term $n lo g n$ really does dominate.

3.10.4 The Generalization of Case 2

Example 4 — $T (n) = 2 T (n /2) + n lo g n$ . Here $a = 2$ , $b = 2$ , $f (n) = n lo g n$ , and:

$n^{l o g_{2} 2} = n$

Now compare: $n lo g n$ is asymptotically larger than $n$ , but the highest power of $n$ in both is 1 — they grow at the same rate up to a log factor. So none of the three standard cases applies cleanly: the functions are not polynomially separated.

There is a generalization for exactly this situation, found in only a few books and carried in the course notes — it is not in the prescribed textbook. If:

$f (n) = Θ (n^{l o g_{b} a} lo g^{k} n) for some k \geq 0$

then:

$T (n) = Θ (n^{l o g_{b} a} lo g^{k + 1} n)$

For example 4, $k = 1$ :

$T (n) = Θ (n lo g^{2} n)$

Q: How is $k + 1$ equal to $k$ in the general case?

A: That was a slip in the write-up — it must be $k + 1$ . With $k = 1$ the exponent becomes $1 + 1 = 2$ , which is how the answer came out as log square. Thanks for pointing it out.

Assumptions & scope of the method: The master method applies only to the divide-and-conquer form $T (n) = a T (n / b) + f (n)$ with constants $a \geq 1$ , $b > 1$ , and an asymptotically positive $f (n)$ . It does not apply when the three cases leave a gap: if $f (n)$ is smaller or larger than $n^{l o g_{b} a}$ but not polynomially so (the $n lo g n$ versus $n$ gap above, or an $f (n) = n / lo g n$ versus $n$ situation), none of the cases matches and the method is silent — the recursion tree or a generalization is needed. Case 3 additionally demands the regularity check $a f (n / b) \leq c f (n)$ ; nearly every polynomially bounded $f (n)$ passes it, but the check must still be written before the answer. Also, floors and ceilings on $n / b$ are ignored by the standard statement: replacing $n / b$ by $⌊ n / b ⌋$ or $⌈ n / b ⌉$ does not change the asymptotic result.

3.10.5 The Concept Behind the Cases

All three cases depend on one comparison: $f (n)$ against $n^{l o g_{b} a}$ . Conceptually, $f (n)$ is the cost incurred at the root of the recursion tree, and $n^{l o g_{b} a}$ is the cost incurred at the leaves. The larger of the two decides the solution. But polynomial growth is the catch — you look at the power of $n$ , not just asymptotic growth — and case 3 carries the regularity check.

No need to memorize the three cases: by this point the concept is understood, and understanding beats memorization.

Q: Do we have to memorize the three cases?

A: No. Understand the comparison between the root cost $f (n)$ and the leaf cost $n^{l o g_{b} a}$ , remember the regularity check for case 3, and the cases follow.

Visual intuition: Recall the two recursion trees of 3.9. The three cases are the three possible shapes of the level-cost series: case 1 is a shrinking geometric series (each level costs less than the one above — leaves win, height of the leaf pile $n^{l o g_{b} a}$ decides); case 2 is a flat series (every level ties, so the total is the per-level cost times $lo g_{b} n$ levels); case 3 is a growing series (the root's $f (n)$ dwarfs everything below). Plot the level costs on the vertical axis against level number on the horizontal axis: the three curves are a downward slide, a flat line, and an upward ramp. One-sentence takeaway: find which of root, leaves, or both-equal decides the tree, and the case — and the answer — follow.

Pitfalls:

Comparing asymptotics instead of powers of $n$ . $n lo g n$ is asymptotically "bigger" than $n$ but has the same power of $n$ — that is a gap, not case 3. Case 3 needs a polynomial gap: $f (n) \geq n^{l o g_{b} a + ε}$ , i.e., a higher power of $n$ .
Writing case 3 without the regularity check. The professor's explicit rule: check $a f (n / b) \leq c f (n)$ for some $c < 1$ before writing the case-3 answer.
Forgetting the log factor in case 2. A tie is not "either function" — the answer is the tied value times one extra log factor.
Using the master method outside its form. It only covers $a T (n / b) + f (n)$ . Recurrences with $T (n - 1)$ terms (factorial, Hanoi), with two different sub-problem sizes, or in the gaps between cases need the iterative method or the recursion tree instead.
Trusting a slip without checking. The $k + 1$ typo was caught by a student asking "how is $k + 1$ equal to $k$ ?" — when your answer's algebra reads oddly, re-derive it rather than copy it.

Exam note: No need to memorize the three cases — but you must be able to compare $f (n)$ with $n^{l o g_{b} a}$ (as functions of the power of $n$ ) and to apply the regularity check in case 3. Understanding the root-versus-leaves comparison beats memorization.

Recap + bridge: The master method answers $T (n) = a T (n / b) + f (n)$ by comparing the root cost $f (n)$ against the leaf cost $n^{l o g_{b} a}$ : polynomially smaller $f (n)$ gives case 1 ( $Θ (n^{l o g_{b} a})$ ), equality gives case 2 ( $Θ (n^{l o g_{b} a} lo g n)$ ), polynomially larger $f (n)$ with the regularity check gives case 3 ( $Θ (f (n))$ ); the log-power generalization handles $f (n) = Θ (n^{l o g_{b} a} lo g^{k} n)$ with $Θ (n^{l o g_{b} a} lo g^{k + 1} n)$ . With the iterative method, the recursion tree, and the master method all in hand, the session's toolkit for solving recurrences is complete — the closing appendices summarize what the quiz expects and what these running times mean in industry.

Real-world connection: the master method is the everyday tool for sizing divide-and-conquer systems before they are built — a database engineer checking a balanced-split join (case 2, $n lo g n$ ), a search team checking a 9-way split index (case 1, $n^{2}$ — the signal to stop splitting), or a distributed merge with heavy combine cost (case 3, the combine term decides). Knowing which case a recurrence falls into is how engineers predict whether doubling data doubles, quasi-doubles, or quadruples the runtime — the same three curves as the recursion-tree shapes, read off in seconds.

Exam Guidance Summary

Time calculations will be asked in the quiz. This was stressed more than once, and the quiz comes after session four. Practice writing recurrences and solving them (iterative method, recursion tree, master method) until the steps are routine.
The quiz runs for one hour and stays open for several days (per the instruction cell's calendar); the date, topics, and window will be announced. Once started, it must be completed in one go.
Terminology is graded: "base operation" earns zero for that term; the correct term is "basic operation."
The basic operation is the statement executing the maximum number of times; in a recursive algorithm, look in the recursive part, not the base case.
No need to memorize the three master-method cases — but you must be able to compare $f (n)$ with $n^{l o g_{b} a}$ (as functions of the highest power of $n$ ) and apply the regularity check in case 3.
Textbook advice: Goodrich is enough for preparation. After the basic understanding is in place, open Cormen — it will sound like Greek and French at first, but read it twice or thrice and it clicks.
Refresh your math: logarithms, arithmetic progressions, geometric progressions (including the GP sum formula) — these power the solutions.
Concepts before computation: the instructor does not like checking math skills in an algorithms exam, so understand the ideas behind the summations (the recursion-tree picture, the root-versus-leaves comparison) rather than memorizing sums.
Homework exercises were posted; work them and post your solutions in the discussion forum. A case study for the master method is also for you to go through.
Assignment 1 and 2 roll out together about fifteen days out: individual work, two questions, and questions may come from post-mid-semester topics too. Start early; the material will be covered in due course — no need to panic when the questions first appear.

Exam note: the single most examinable skill from this session is the time calculation: pick the size parameter, identify the basic operation, write the two-case recurrence, solve it, and state the order of growth. The terminology points ("basic operation", never "base operation") and the master-method comparison skill are the other two things the quiz checks.

Key Industry Applications

Real-world: when you are running an algorithm or a program at work, you rarely state an exact running time — you give an approximation, and it is always safer to give an upper bound ("I might take ten minutes" rather than five). This is the same reasoning that prefers big-O in analysis: some slack always remains because only the basic operation is counted. In practice this is how engineers set capacity expectations: when a service owner is asked "how long will this batch job take?", the honest answer is an upper-bound estimate computed from the order of growth — $O (n)$ for a one-pass job, $O (n lo g n)$ for a sort, $O (2^{n})$ for something exponential — because exact constants depend on hardware, compiler, and input distribution that are never known precisely at planning time.

Real-world: exponential time complexity means the algorithm performs on the order of $2^{n}$ computations even for relatively small $n$ — $n = 10$ or 15 is already expensive. For some problems, like Tower of Hanoi, no better algorithm is known, and the problem itself must be accepted as computationally expensive; but whenever a linear-time algorithm exists for a problem, it is the one to write. In industry, this is the difference between a product feature that ships (linear or $n lo g n$ scans over records) and one that dies in review (an exponential recursion over inputs of size 30+): the recurrence analysis done in this session is the same arithmetic used to reject exponential designs before they are built — and the same arithmetic that justifies accepting them when the problem's nature leaves no faster route (for example, certain search and optimization problems where the exponential algorithm is the known best).

DSA Lecture 3 notes · Analyzing Recursive Algorithms

Data Structures and Algorithms· postgraduate· 2026-08-09

Sections Breakdown

13.1 Recursion and the Base Case

What recursion really means — a procedure calling itself on strictly smaller sub-problems — and the base case that stops the call chain.

23.2 Recursive Maximum: The First Worked Example

The recursive maximum-finding algorithm, read line by line, with a full hand trace on a concrete array.

33.3 Recurrence Equations and the Iterative Method

Writing a recursive algorithm's running time as a two-case recurrence and solving it by repeated substitution to a closed form.

43.4 The General Plan and the Shift to Basic Operations

The five-step plan for analyzing any recursive algorithm, and the switch from primitive operations to the single basic operation.

53.5 Factorial: Basic Operations in Action

Factorial's multiplication-based recurrence T(0)=0, T(n)=T(n-1)+1 solved to exactly n, giving Theta(n).

63.6 Tower of Hanoi

The classic three-step recursive solution and its recurrence M(n)=2M(n-1)+1, closed with a geometric-progression sum to 2^n - 1.

73.7 Counting Binary Digits

A halving recursion analyzed under the power-of-two assumption, giving A(n) = log2 n = Theta(log n), and the correct term: basic operation.

83.8 The Methods for Solving Recurrences

The menu of solving methods — iterative, recursion tree, master — and why the substitution method is deferred.

93.9 The Recursion Tree Method

Drawing a recurrence as a tree of sub-problem costs: heights, leaf counts, and level-cost sums for 3T(n/4)+cn^2 and 2T(n/2)+n.

103.10 The Master Method

The three cases of the master method for T(n)=aT(n/b)+f(n), the regularity check, and the case-2 generalization with log powers.

11Exam Guidance Summary

The exam-facing summary of the session: quiz timing, graded terminology, and the skills the quiz checks.

12Key Industry Applications

How upper-bound running-time estimates and recurrence analysis decide what ships in real systems.

Postgraduate students learning to analyze recursive algorithms

Exam Revision Notes

Below is the distilled, exam-ready core. Every entry comes from the full explanation above. Use this section for rapid review; return to the main notes when a point needs more context.

Recursion and the Base Case

Must-know: Every recursive algorithm has two parts: a base case (smallest instance, answered directly) and an otherwise case (recursive call on a strictly smaller sub-problem); the shrinking is what guarantees the recursion stops.

Top pitfall: Forgetting the base case or recursing on the same size instead of a smaller size causes infinite recursion; also do not confuse 'base case' with 'basic operation'.

Self-check: Why must every recursive call work on a strictly smaller input size?

Connects to: 3.2

Recursive Maximum: The First Worked Example

Must-know: recursiveMax(a,n) = max(recursiveMax(a,n-1), a[n-1]) with base case return a[0] when n=1; trace by expanding calls down to the base case, then unwinding values back up.

$max (recursiveMax (a, n - 1), a [n - 1])$

Top pitfall: Evaluating max before the recursive call's value is known, or thinking each call re-scans the whole array.

Self-check: What is the base case of recursiveMax and what does it return?

Connects to: 3.1, 3.3

Recurrence Equations and the Iterative Method

Must-know: Write the recurrence with two cases (constant base case, recursive term plus per-level work), then solve by repeated substitution: T(n)=T(n-1)+7 gives T(n)=7n-4=O(n).

$T (n) = T (n - 1) + 7, T (1) = 3 ⟹ T (n) = 7 n - 4 = O (n)$

Top pitfall: Closing the general form at T(0), which the recurrence never defines; stop at the known base case (i = n-1 here).

Self-check: After i substitutions, what is the general form of T(n) = T(n-1) + 7, and which i closes it?

Connects to: 3.2, 3.4, 3.5

The General Plan and the Shift to Basic Operations

Must-know: The five-step plan: (1) size parameter n, (2) count executions of the basic operation, (3) base case, (4) recurrence, (5) solve and state asymptotics. The basic operation is the statement executing the maximum number of times; in recursive algorithms it lives in the recursive part, not the base case.

Top pitfall: Looking for the basic operation in the base case, or counting all primitive operations instead of the single dominating statement.

Self-check: Where do you look for the basic operation in a recursive algorithm?

Connects to: 3.3, 3.5, 3.7

Factorial: Basic Operations in Action

Must-know: Basic operation of factorial is the multiplication; T(0)=0, T(n)=T(n-1)+1 solves to exactly n, hence Theta(n). The base case's value is 0 because no multiplication happens there.

$T (0) = 0, T (n) = T (n - 1) + 1 ⟹ T (n) = n = Θ (n)$

Top pitfall: Guessing the base case from the return value (1 or 2) instead of the basic-operation cost (0), or counting the recursive call itself as an extra operation.

Self-check: After i substitutions, T(n) = i + T(n-i); why is i = n the right stopping point here?

Connects to: 3.3, 3.4, 3.6

Tower of Hanoi

Must-know: M(1)=1, M(n)=2M(n-1)+1; after i expansions M(n)=2^i M(n-i)+(2^i-1); the tail is a GP with first term 1 and ratio 2 summing to 2^i-1; with i=n-1 the closed form is M(n)=2^n-1=O(2^n). The +1 is a real move of the largest disk.

$M (n) = 2 M (n - 1) + 1, M (1) = 1 ⟹ M (n) = 2^{n} - 1 = O (2^{n})$

Top pitfall: Dropping the +1 (it pays for moving the largest disk, unrelated to the base case) or failing to recognize the tail as a geometric progression.

Self-check: Why does the tail 1+2+4+...+2^(i-1) sum to 2^i - 1?

Connects to: 3.3, 3.5, 3.9

Counting Binary Digits

Must-know: Basic operation is the halving; A(1)=0, A(n)=A(n/2)+1. Assume n=2^k, then A(2^k)=A(2^(k-i))+i, close at i=k with A(1)=0 to get A(2^k)=k; convert back to A(n)=log2 n = Theta(log n). Term on the exam: basic operation, never 'base operation'.

$A (1) = 0, A (n) = A (n /2) + 1 ⟹ A (n) = lo g_{2} n = Θ (lo g n)$

Top pitfall: Writing 'base operation' instead of 'basic operation' (cut to zero), or leaving the answer as k instead of converting back to log2 n.

Self-check: Why is A(1)=0 under the basic-operation method?

Connects to: 3.4, 3.9

The Methods for Solving Recurrences

Must-know: Four methods exist: iterative, substitution (skipped — it needs a guess first), recursion tree, and master method (the easiest).

Top pitfall: Trying the substitution method without being able to guess the answer; the professor defers it for exactly this reason.

Self-check: Why is the substitution method skipped in this session?

Connects to: 3.3, 3.9, 3.10

The Recursion Tree Method

Must-know: Tree height comes from n/b^H = 1, so H = log_b n; level i has a^i nodes of size n/b^i; leaves number n^(log_b a). If level costs form a geometric series with ratio < 1 the root dominates (3T(n/4)+cn^2 gives O(n^2)); if every level costs the same, total is level cost times log n levels (2T(n/2)+n gives Theta(n log n)).

$H = lo g_{b} n, 3^{H} = n^{l o g_{4} 3}, T (n) = c n^{2} + \frac{3}{16} c n^{2} + (\frac{3}{16})^{2} c n^{2} + \dots = O (n^{2})$

Top pitfall: Forgetting that each level-i node's cost shrinks to c(n/4^i)^2; or concluding 'root dominates' without summing the series.

Self-check: Why is the height of the tree for T(n)=3T(n/4)+cn^2 equal to log4 n?

Connects to: 3.10, 3.7

The Master Method

Must-know: For T(n)=aT(n/b)+f(n) with a>=1, b>1: compute n^(log_b a); f polynomially slower -> case 1 Theta(n^(log_b a)); equal -> case 2 Theta(n^(log_b a) log n); polynomially faster + regularity af(n/b)<=cf(n), c<1 -> case 3 Theta(f(n)). Generalization: f(n)=Theta(n^(log_b a) log^k n) gives Theta(n^(log_b a) log^(k+1) n).

$T (n) = a T (n / b) + f (n) ⟹ T (n) = Θ (n^{l o g_{b} a}) or Θ (n^{l o g_{b} a} lo g n) or Θ (f (n))$

Top pitfall: Calling n log n 'bigger' than n is not case 3 — the gap must be polynomial (a higher power of n); and case 3 requires the regularity check before writing the answer.

Self-check: Which case applies to T(n)=9T(n/3)+n and why?

Connects to: 3.9, 3.3

Exam Guidance Summary

Must-know: Quiz after session four, one hour, completed in one go; time calculations will be asked; terminology graded; Goodrich enough for preparation, Cormen after; refresh logarithms, APs and GPs including the GP sum formula.

Top pitfall: Writing 'base operation' instead of 'basic operation' earns zero for that term.

Self-check: Which textbook is enough for preparation and which is recommended after basic understanding?

Key Industry Applications

Must-know: Give an upper-bound estimate of running time at work (like big-O); write the linear algorithm whenever one exists; accept exponential only when no better algorithm is known.

Top pitfall: Claiming only an exponential-time algorithm exists when a linear one does.

Self-check: Why is it safer to give an upper bound for a running time estimate?

Previous LectureLecture 02 · Algorithm Analysis: From Basic Operations to Asymptotic Notation

Next LectureLecture 04 · Abstract Data Types: Stacks, Queues, Lists, and Vectors

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.

Prerequisite Knowledge

Previously Covered in This Subject

3.1 Recursion and the Base Case

3.1.1 What Recursion Really Means

3.1.2 The Base Case

3.2 Recursive Maximum: The First Worked Example

3.2.1 The Algorithm

3.2.2 The Trace, Step by Step

3.3 Recurrence Equations and the Iterative Method

3.3.1 What a Recurrence Is

3.3.2 Writing the Recurrence for Recursive Maximum

3.3.3 Solving the Recurrence with the Iterative Method

3.4 The General Plan and the Shift to Basic Operations

3.4.1 The Five-Step Plan

3.4.2 Primitive Operations Are Out; Basic Operations Are In

3.5 Factorial: Basic Operations in Action

3.5.1 The Algorithm and Its Recurrence

3.5.2 Solving the Recurrence

3.6 Tower of Hanoi

3.6.1 The Problem

3.6.2 The Recursive Algorithm

3.6.3 Recurrence and Analysis

3.7 Counting Binary Digits

3.7.1 The Algorithm and Its Recurrence

3.7.2 The Power-of-Two Assumption

3.7.3 The Right Term: Basic Operation

3.8 The Methods for Solving Recurrences

3.8.1 The Menu of Methods

3.8.2 Why the Substitution Method Is Skipped

3.9 The Recursion Tree Method

3.9.1 The Idea of the Recursion Tree

3.9.2 Worked Example: Three Subproblems of Size n/4

3.9.3 Worked Example: Two Subproblems of Size n/2

3.10 The Master Method

3.10.1 The General Form

3.10.2 The Three Cases

3.10.3 Worked Examples

3.10.4 The Generalization of Case 2

3.10.5 The Concept Behind the Cases

Exam Guidance Summary

Key Industry Applications

DSA Lecture 3 notes · Analyzing Recursive Algorithms

Sections Breakdown

Exam Revision Notes

Recursion and the Base Case

Recursive Maximum: The First Worked Example

Recurrence Equations and the Iterative Method

The General Plan and the Shift to Basic Operations

Factorial: Basic Operations in Action

Tower of Hanoi

Counting Binary Digits

The Methods for Solving Recurrences

The Recursion Tree Method

The Master Method

Exam Guidance Summary

Key Industry Applications

Was this lecture useful?

BitsNotes AI Assistant

Configure AI Chat

Sign in to use AI Chat