Master theorem — solving recurrences T(n) = aT(n - b) + f(n): Question bank

Definition Symbols this page assumes (built before use)

The recurrence is $T (n) = a T (n / b) + f (n)$ with these standard preconditions:

$a \geq 1$ (number of subproblems) and $b > 1$ (shrink factor) are constants, not functions of $n$ .
$f (n) > 0$ asymptotically (the work outside recursion: split + combine).
$n$ is treated as a suitable power of $b$ ; non-powers are handled by $Θ (1)$ rounding (floors/ceilings) that doesn't change the asymptotics.

The critical exponent is $c_{crit} = lo g_{b} a$ , so $n^{c_{crit}} = n^{l o g_{b} a}$ is the total leaf cost. Everything races $f (n)$ against this number.

The parameter $k$ appears only in Case 2: it is the exponent on a $lo g$ factor riding on $f$ , i.e. $f (n) = Θ (n^{l o g_{b} a} lo g^{k} n)$ with $k \geq 0$ . Then $T (n) = Θ (n^{l o g_{b} a} lo g^{k + 1} n)$ .

The regularity condition (needed only for Case 3) is: there exists a constant $c < 1$ with $a f (n / b) \leq c f (n)$ for large $n$ . It guarantees the level costs shrink geometrically toward the root.

Remember the one ruler the whole theorem races on: compare $f (n)$ against $n^{l o g_{b} a}$ . " $f$ polynomially smaller (i.e. $f = O (n^{l o g_{b} a - ϵ})$ for some $ϵ > 0$ ) → leaves win", " $f$ equal → tie, add a $lo g$ ", " $f$ polynomially bigger → root wins". Every trap below is a way that ruler gets misread.

True or false — justify

Master Theorem applies to

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

False. The two subproblems have different sizes (

n /3

and

2 n /3

), so there is no single

a, b

pair. Use Recursion Trees or the Akra–Bazzi method instead.

c_{crit} = lo g_{b} a

depends on the input size

n

False.

a

and

b

are fixed constants from the recurrence, so

lo g_{b} a

is a single number computed once — it never varies with

n

f (n)

is bigger than

n^{l o g_{b} a}

, the answer is always

Θ (f (n))

False. "Bigger" must be polynomially bigger (

Ω (n^{l o g_{b} a + ϵ})

) and the regularity condition

a f (n / b) \leq c f (n)

c < 1

, must hold. A mere

lo g

factor bigger falls in the gap and is not Case 3.

In Case 2, the extra

lo g

comes from the number of levels in the tree.

True. Every level costs about

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

and there are

lo g_{b} n

levels, so total

=

level-cost

\times

number of floors, giving an extra

lo g

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

is Case 3 because

f (n) = n^{2}

is large.

False. Here

c_{crit} = lo g_{2} 4 = 2

, so

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

, which equals

f (n)

. It is Case 2 with

k = 0

(no log rides on

f

Θ (n^{2} lo g n)

, not Case 3.

The number of leaves in the recursion tree is

n^{l o g_{b} a}

True. There are

a^{l o g_{b} n}

leaves, and the log identity

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

rewrites this as the leaf cost

n^{l o g_{b} a}

Case 1 requires the regularity condition.

False. Only Case 3 (root wins) needs regularity (

a f (n / b) \leq c f (n)

c < 1

) to guarantee the geometric series converges to the root. Case 1's series is dominated by the leaves and converges automatically.

Master Theorem can handle

f (n)

that is sometimes negative.

False. The derivation sums level costs as positive work;

f (n)

must be positive asymptotically for the geometric-series comparison to make sense.

For

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

, the answer is

Θ (n lo g n)

False.

n lo g n

beats

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

only by a

lo g

factor, not polynomially, so it is not Case 3. Extended Case 2 with

k = 1

gives

Θ (n lo g^{2} n)

If two recurrences have the same

a

and

b

but different

f (n)

, they can land in different cases.

True.

a, b

fix

n^{l o g_{b} a}

, but which case wins depends entirely on how

f (n)

compares to it, so different

f

can give Case 1, 2, or 3.

Spot the error

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

, and since

n

grows, root dominates →

Θ (n)

Wrong:

c_{crit} = lo g_{2} 3 \approx 1.585 > 1

, so the leaf cost

n^{1.585}

beats

f (n) = n

. This is Case 1:

Θ (n^{l o g_{2} 3})

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

is Case 1 because

f (n) = 1

is tiny."

Wrong:

c_{crit} = lo g_{2} 1 = 0

, so

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

, which equals

f (n) = 1

. It is a tie → Case 2 →

Θ (lo g n)

, not

Θ (1)

"For Case 3 I only need

f (n) = Ω (n^{l o g_{b} a + ϵ})

; regularity is optional detail."

Wrong: without

a f (n / b) \leq c f (n)

(

c < 1

), a badly oscillating

f

can make the series not converge to the root, so the

Θ (f (n))

conclusion can fail.

c_{crit} = lo g_{a} b

Wrong: it is

lo g_{b} a

— base

b

(the shrink factor), argument

a

(the branching count). Swapping them inverts the exponent and breaks every case.

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

is a tie because both have degree 2 somewhere."

Wrong:

c_{crit} = 1

, so leaf cost is

n^{1}

, while

f = n^{2}

. That is polynomially bigger, and regularity holds (

\frac{1}{2} < 1

), so it is Case 3:

Θ (n^{2})

"Karatsuba

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

gives

Θ (n^{2})

, matching schoolbook multiplication."

Wrong:

c_{crit} = lo g_{2} 3 \approx 1.585

, and Case 1 gives

Θ (n^{1.585})

— strictly faster than the schoolbook

n^{2}

; that speedup is the whole point of Karatsuba Multiplication.

Why questions

Why do we compare

f (n)

specifically to

n^{l o g_{b} a}

and not to

n

n^{2}

Because

n^{l o g_{b} a}

is the exact total cost of the leaves; the whole recurrence is a race between leaf work and root work, so that is the meaningful yardstick.

Why does a "log gap" (like

n lo g n

n

) escape the basic theorem?

The three cases are built from a geometric series that needs a polynomial ratio to decide direction; a

lo g

factor changes the ratio too slowly to force convergence either way, leaving a gap.

Why does Case 2 need

f = Θ

(both

O

and

Ω

) rather than just

O

Ω

A tie means

f

matches

n^{l o g_{b} a}

from both sides; being only

\leq

or only

\geq

would push it toward Case 1 or Case 3 instead.

Why do the leaves dominate in Case 1?

When

f

shrinks faster going up the tree, the per-level costs form a series that increases toward the bottom, so the sum is controlled by the huge number of tiny leaf subproblems (see Geometric Series).

Why is

lo g_{b} n

the number of levels?

The size shrinks by factor

b

each level and bottoms out at 1, so

n / b^{L} = 1 \Rightarrow L = lo g_{b} n

— that is how many times you can divide

n

b

before reaching 1.

Why does Case 3's answer drop the

lo g_{b} n

levels entirely?

When the root dominates, the level costs form a decreasing geometric series whose sum is a constant multiple of the first term

f (n)

, so the lower levels contribute only a constant factor, not a

lo g

Why is the regularity condition automatically satisfied for polynomial

f (n)

For

f (n) = n^{d}

a f (n / b) = a n^{d} / b^{d} = (a / b^{d}) f (n)

, and being in Case 3 forces

a / b^{d} < 1

, so

c = a / b^{d} < 1

works directly.

Edge cases

What happens when

a = 1

Then

c_{crit} = lo g_{b} 1 = 0

and the leaf cost is

n^{0} = 1

; you have a single shrinking chain (like Binary Search), so you compare

f (n)

against a constant.

What happens when

f (n) = 0

or negative asymptotically?

The theorem does not apply — the derivation sums positive work per level, so a non-positive

f

breaks the geometric-series argument entirely.

What if

a

b

is not a constant (e.g. depends on

n

Master Theorem is invalid; its whole structure assumes fixed branching and shrink factors, so you must fall back to Recursion Trees or Akra–Bazzi method.

What if

b \leq 1

Also invalid — with

b = 1

the input never shrinks and with

b < 1

it grows, so there is no finite tree of depth

lo g_{b} n

; the precondition

b > 1

is essential.

What if

f (n)

sits exactly on the boundary but with

k < 0

(i.e.

f = n^{l o g_{b} a} lo g^{k} n

with negative

k

, like

n^{l o g_{b} a} / lo g n

The basic

k \geq 0

Case 2 does not cover it; this needs the finer extended results (or Akra–Bazzi), because the negative-power log changes how the series sums.

T (n) = 2 T (n /2) + n^{1.99}

Case 3, given that

1.99

is close to

c_{crit} = 1

Yes, Case 3 —

1.99 > 1

, and any fixed positive gap (

ϵ = 0.99

) makes

f

polynomially bigger; closeness to

c_{crit}

doesn't matter, only that the gap is positive and constant, so the root wins with

Θ (n^{1.99})

Does Master Theorem tell you the constant factor hidden in

Θ

No — it only gives the asymptotic growth class; the leading constant depends on the exact costs and is outside what the theorem resolves.

Connections

Recursion Trees — the picture every "why" answer here points back to.
Akra–Bazzi method — the escape hatch for unequal subproblems and non-constant splits.
Big-O, Big-Omega, Big-Theta — the $O /Ω/Θ$ language every trap is phrased in.
Geometric Series — why "increasing / flat / decreasing" is the real classifier.
Merge Sort, Binary Search, Karatsuba Multiplication — the applications the traps quietly test.