SME
Data Structures & Algorithms · Problem type
The master theorem
Use this for “Solve T(n) = 8T(n ÷ 2) + Θ(n²) with the master theorem.”
This is an example. Type your own values to start a new problem.
T(n)
=
a
T(n
÷
b
)
+
Θ(
n
)
c
Critical exponent
worked out (not typed)
D
Dominant work
worked out (not typed)
k
Power of n
worked out (not typed)
Formulas
c
=
ln(
a
)
ln(
b
)
3
=
ln(8)
ln(2)
D
:
compare
c
with
d
3 > 2, so leaves dominate
k
=
max(
c
,
d
)
3 = max(3, 2)
Assumptions
•
T(n) = aT(n ÷ b) + Θ(nᵈ): each call on size n makes a calls on size n ÷ b and does nᵈ work itself.
•
The recursion tree has nᶜ leaves, where c = logb a, the critical exponent.
•
The larger of c and d sets the growth; a tie adds one log n factor, one for each level.
•
With work nᵈ the regularity condition of the third case always holds.
Step-by-step
WE KNOW
a = 8, b = 2, d = 2
FIND
critical exponent (c), dominant work (D), power of n (k)
Step 1 · Find critical exponent (c)
Use c = ln(a) ÷ ln(b)
Each
level
multiplies
the
calls
by
a
and
divides
the
size
by
b
,
so
the
leaves
number
nᶜ.
c
=
ln(8)
ln(2)
c
=
2.079
0.6931
c
=
3
Step 2 · Find dominant work (D)
Use D: compare c with d
The work grows level by level down the tree, so the leaves hold most of it.
3 > 2: leaves dominate
D
=
compare
3
with
2
D
=
leaves
dominate
Step 3 · Find power of n (k)
Use k = max(c, d)
The power of n in the answer is the larger exponent.
k
=
max(3,
2)
k
=
3
→
T(n)
=
Θ(
n
3
)
Check
Put the numbers back in. Both sides should match.
3
=
ln(8)
ln(2)
✓
3 > 2, so leaves dominate ✓
3 = max(3, 2) ✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.