Recursion tree method: Question bank — Coding deep dive

First: the notation these traps use

Every question below lives inside one master recurrence, so let us name each symbol once, in plain words, before it appears anywhere else.

Definition The symbols on this page

We study $T (n) = a T (n / b) + f (n)$ , where:

$n$ = the input size of the top-level problem (how big the job is).
$a$ = the branching factor: how many smaller sub-problems each call creates. In the picture, $a$ is how many arrows leave a node going down.
$b$ = the shrink factor: each sub-problem is $1/ b$ the size of its parent. In the picture, $b$ controls how fast sizes drop as you go down.
$f (n)$ = the non-recursive work: the effort one call does itself, not counting its children. This is the number written inside a node.
$i$ = the level index: how many steps down from the top you are. We count the root as level $0$ , its children as level $1$ , and so on — this " $0$ -based" convention is what the later " $+ 1$ " traps hinge on.
$d$ = the exponent when $f (n) = n^{d}$ is a plain power of $n$ (e.g. $f (n) = n^{2}$ means $d = 2$ ).

Look at the figure: it labels all six symbols on a small tree so the words attach to a picture.

Formula Where

$a^{i} f (n / b^{i})$ comes from (the one formula every trap uses) WHAT: the total work done by all nodes sitting at level $i$ . WHY it takes this shape, step by step:

How many nodes at level $i$ ? The root ( $i = 0$ ) is $1$ node. Each node has $a$ children, so level $1$ has $a$ , level $2$ has $a \cdot a = a^{2}$ , and in general $a^{i}$ nodes. (This is just the exponent law $a \cdot a \dots a$ , $i$ times $= a^{i}$ .)
How big is each node at level $i$ ? The size divides by $b$ each step down: $n \to n / b \to n / b^{2} \to \dots \to n / b^{i}$ . (Again exponent law: dividing by $b$ , $i$ times, is dividing by $b^{i}$ .)
How much work does one such node do? Its own non-recursive cost is $f$ evaluated at its size, i.e. we substitute the size $n / b^{i}$ into the function: $f (n / b^{i})$ .
Multiply count $\times$ per-node work: $W (i) = nodes a^{i} \times work each f (\frac{n}{b ^{i}}) .$ The two exponent facts (how many, how small) meet the function substitution (what $f$ does at that size) — that interaction is the whole formula.

The figure below shows the level sums as a bar per level, so you can see whether they grow, stay flat, or shrink downward — the single distinction that decides every trap.

True or false — justify

Every level of a recursion tree costs the same as the root, so total work is

f (n) \cdot lo g n

False. Level

i

costs

a^{i} f (n / b^{i})

, not

f (n)

. It only stays flat when

a^{i}

exactly cancels the shrink in

f

(as in Merge Sort); otherwise the level sums grow or shrink geometrically.

A recursion tree always has exactly

n

leaves.

False. The number of leaves is

a^{l o g_{b} n} = n^{l o g_{b} a}

. It equals

n

only when

a = b

; for

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

it is

n^{l o g_{2} 3} \approx n^{1.58}

If per-level work is a decreasing geometric series, the total is dominated by the leaves.

False. Decreasing means the first term (the root) is largest, so the root dominates and

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

. Leaves dominate only when the series increases downward.

The depth of the tree depends on the branching factor

a

False. Depth is set by how fast the size shrinks, i.e.

b

: solving

n / b^{i} = 1

gives

i = lo g_{b} n

. The factor

a

controls the width (

a^{i}

nodes), not the number of levels.

For

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

the answer is

Θ (n lo g n)

purely because there are

lo g n

levels.

False. It is

lo g n

levels times the per-level work

n

. If a single level cost more or less, the answer would change even with the same depth.

Adding a constant number of levels (like counting from

0

lo g_{b} n

inclusive) changes the asymptotic answer.

False. With the root at level

0

, the last level is

lo g_{b} n

, so there are

lo g_{b} n + 1

levels. Concretely for

n = 8, b = 2

: that is

lo g_{2} 8 + 1 = 4

levels vs

3

— a factor

4/3

, a constant. Since

Θ

ignores constant multipliers,

n (lo g_{2} n + 1)

and

n lo g_{2} n

are both

Θ (n lo g n)

Floors and ceilings on the subproblem size can change the asymptotic answer.

False (for these divide-and-conquer recurrences). Replacing

n / b

⌊ n / b ⌋

⌈ n / b ⌉

shifts each size by less than

1

, perturbing depth and per-level work by only constant factors, which

Θ (\cdot)

absorbs. That is why we analyse the clean

n / b^{i}

and still get the right order.

In an unbalanced recurrence, you must find the exact number of nodes to solve it.

False. You bound the per-level work and the height range instead. For

T (n /3) + T (2 n /3) + n

, each level sums to

\leq n

and height is

Θ (lo g n)

, giving

Θ (n lo g n)

without counting nodes.

a = b^{d}

for

f (n) = n^{d}

, the per-level work is constant and the total gains a

lo g

factor.

True. The per-level ratio is

a / b^{d} = 1

, so every level does the same work

Θ (n^{d})

, and summing over

lo g_{b} n

levels gives

Θ (n^{d} lo g n)

Spot the error

"Level

i

has

a^{i}

nodes each of size

n / b^{i}

, so its work is

a^{i} \cdot n / b^{i}

for any

f

Wrong — that assumes

f

is linear. The general level work is

a^{i} f (n / b^{i})

; you substitute the size into

f

. Only when

f (m) = m

does it simplify to

a^{i} n / b^{i}

"The ratio deciding the three cases is

a / b

Wrong — for

f (n) = n^{d}

the ratio is

a / b^{d}

, not

a / b

. The exponent

d

from

f

must appear; ignoring it misclassifies cases like

T (n) = 3 T (n /4) + n^{2}

(

r = 3/16

, not

3/4

"Since merge sort has

n

leaves and

n

work per level, its total is

n \cdot n = n^{2}

Wrong — you don't multiply leaves by per-level work. You sum per-level work over all levels:

n \times (lo g_{2} n + 1) = Θ (n lo g n)

. Leaf count is one level's contribution, not a multiplier.

"For

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

I'll use

b = 3

because that's the first fraction."

Wrong — the branches shrink at different rates, so there is no single

b

. The longest (slowest) branch

2 n /3

sets the depth

lo g_{3/2} n

, and you bound per-level work separately.

"A decreasing geometric series with infinitely many terms sums to infinity, so I can't bound the root case."

Wrong — a geometric series with ratio

r < 1

converges to a finite constant times its first term (

\frac{1}{1 - r}

, see Geometric Series). That's exactly why the root's cost dominates.

"Binary Search recurrence

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

has

lo g n

levels each doing

lo g n

work, so

Θ (lo g^{2} n)

Wrong — each level does

Θ (1)

work (there is only one node per level, and

f = 1

). Summing

1

over

lo g n

levels gives

Θ (lo g n)

"For

f (n) = n lo g n

the ratio is still

a / b^{d}

, so I can read off the case."

Wrong —

n lo g n

is not a pure power

n^{d}

, so no single

d

exists. You must plug it into

a^{i} f (n / b^{i})

directly and sum; the clean

a / b^{d}

shortcut only applies to

f (n) = Θ (n^{d})

"Because

n / b^{i}

isn't a whole number, the recursion tree method is invalid."

Wrong — the tree gives the correct order despite the fractions. Floors/ceilings change sizes by less than

1

, altering the result by only constant factors that

Θ (\cdot)

ignores; a full proof uses substitution with the ceiling.

Why questions

Why does the tree level method give the same three cases as the Master Theorem?

Because the level sums

n^{d} (a / b^{d})^{i}

form a geometric series whose ratio decides everything:

< 1

(root),

= 1

(balanced/

lo g

> 1

(leaves) — that's precisely the Master Theorem's three cases, derived not memorized.

Why do we write only the non-recursive cost

f (m)

in each node?

Because the recursive calls are represented by the node's children, not by its own label. Including them would double-count — the tree already unfolds the recursion structurally.

Why is the number of leaves

n^{l o g_{b} a}

rather than something involving

f

Leaf count depends only on how the problem splits — branching

a

over depth

lo g_{b} n

— giving

a^{l o g_{b} n} = n^{l o g_{b} a}

. The work function

f

affects per-node cost, not how many nodes exist.

Why can an algorithm with more branches (

a

) still be slower-growing than one with fewer, if

f

differs?

Growth is a tug-of-war between splitting (

a

b

) and per-call work (

f = n^{d}

) via the ratio

a / b^{d}

. Large

a

can be beaten by a large

d

, so branching alone doesn't decide dominance.

Why does the longest branch, not the shortest, determine the height of an unbalanced tree?

The tree isn't done until every branch reaches the base case; the slowest-shrinking branch is the last to finish, so it fixes the maximum depth (and the height bound you use).

Why is it safe to ignore floors and ceilings when reading off a

Θ

answer?

Rounding a size up or down changes it by less than

1

, so depth and per-level work move by only constant factors — and

Θ (\cdot)

is defined to ignore constant factors. The clean

n / b^{i}

analysis therefore lands on the correct order.

Why is finding the per-level ratio more reliable than "just counting levels"?

Counting levels only helps in the balanced case where each level costs the same. The ratio tells you whether levels are balanced, growing, or shrinking — without it you can't know if a

lo g

factor even applies.

Why does

f (n) = n lo g n

not fit the neat three-case table, and what does the tree give instead?

Because

lo g n

isn't a power of

n

, the level sums aren't a clean geometric series. Substituting into

a^{i} f (n / b^{i})

and summing (e.g. for

2 T (n /2) + n lo g n

) yields

Θ (n lo g^{2} n)

— a result the pure

n^{d}

table can't produce.

Edge cases

What happens to the tree when

a = 1

(only one subproblem per call), as in Binary Search?

The tree becomes a single path, not a branching tree:

1

node per level,

lo g_{b} n

levels. Total is just the sum of

f

along that path.

What if

f (n) = Θ (1)

(constant work per call)?

Then per-level work is

a^{i} \cdot Θ (1) = Θ (a^{i})

, which grows with depth whenever

a > 1

. The leaves dominate and

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

— pure branching cost.

What if

f (n)

is not a power of

n

, e.g.

f (n) = n lo g n

Substitute directly:

W (i) = 2^{i} \cdot \frac{n}{2 ^{i}} lo g \frac{n}{2 ^{i}} = n lo g (n / 2^{i})

, which sums over

lo g n

levels to

Θ (n lo g^{2} n)

. The tree still works even when the

a / b^{d}

shortcut does not apply.

What if

b = 1

(subproblem size never shrinks)?

The recursion never reaches a base case; the depth

lo g_{b} n

is undefined (division by

lo g 1 = 0

). The tree has infinite depth — the recurrence doesn't describe a terminating algorithm.

What if

n

is not a power of

b

, so

n / b^{i}

is fractional at some level?

The real tree uses

⌊ n / b ⌋

⌈ n / b ⌉

, so branch sizes differ by at most

1

and the depth by at most one extra level. These are constant-factor effects, so the

Θ

answer computed from the ideal

n / b^{i}

still holds.

At the base case, why do we say each leaf costs

Θ (1)

instead of

f (1)

literally?

Because

f (1)

is some fixed constant, and constants are

Θ (1)

under Big-O Notation. What matters is the count of leaves (

n^{l o g_{b} a}

) times that constant.

What is the effect of an additive constant in the recurrence, e.g.

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

The

+ 5

is dominated by

n

at every node, so

f (n) = Θ (n)

and the analysis is unchanged — total stays

Θ (n lo g n)

. Lower-order terms vanish asymptotically.

In the balanced case, does the tree depth being

lo g_{b} n

lo g_{b} n + 1

change the

lo g

factor?

No — both are

Θ (lo g_{b} n)

, and changing the log base only multiplies by a constant (

lo g_{b} n = lo g_{2} n / lo g_{2} b

). The final

Θ (n^{d} lo g n)

is base-independent.

Connections

Master Theorem — every trap here maps to one of its three cases.
Divide and Conquer — the tree is the natural picture of splitting problems.
Substitution Method — the algebraic partner: guess from the tree, prove by substitution (and rigorously handle floors/ceilings).