Introduction to Algorithms

Lecture 2: Asymptotic Notation

Prof. Charles E. Leiserson and Prof. Erik Demaine

Massachusetts Institute of Technology

July 30, 2025

Introduction to Algorithms Lecture 2 1 / 80

Introduction to Algorithms

Content has been extracted from Introduction to Algorithms, Fourth Edition, by Cormen,
Leiserson, Rivest, and Stein. MIT Press. 2022.
Visit [Link]
Original slides from Introduction to Algorithms 6.046J/18.401J, Fall 2005 Class by Prof. Charles
Leiserson and Prof. Erik Demaine. MIT OpenCourseWare Initiative available at
[Link]

Introduction to Algorithms Lecture 2 2 / 80

Plan

Asymptotic Notation

Solving recurrences
Substitution method
Recursion tree
The master method

Introduction to Algorithms Lecture 2 3 / 80

Asymptotic Notation

We write f (n) = O(g(n)) if there exist such constants

c > 0, n0 > 0 such that 0 ≤ f (n) ≤ cg(n) for all n ≥ n0 .

Introduction to Algorithms Lecture 2 4 / 80

O-notation (upper bounds)

O(g(n)) = {f (n) : there exist constants

c > 0, n0 > 0 such that
0 ≤ f (n) ≤ cg(n)
for all n ≥ n0 }
54 Chapter 3 Characterizing Running Times

cg.n/
f
f .n/
c

n
n0 n0
f .n/ D O.g.n// f .n/ D �.g.n
Introduction to Algorithms Lecture 2 5 / 80
O-notation (upper bounds)

O(g(n)) = {f (n) : there exist constants

c > 0, n0 > 0 such that
0 ≤ f (n) ≤ cg(n)
for all n ≥ n0 }

Example
2n2 = O(n3 ) (c = 1, n0 = 2).

Introduction to Algorithms Lecture 2 6 / 80

O-notation (upper bounds)

O(g(n)) = {f (n) : there exist constants

c > 0, n0 > 0 such that
0 ≤ f (n) ≤ cg(n)
for all n ≥ n0 }

Example
2n2 = O(n3 ) (c = 1, n0 = 2).

Functions,
not values!

Introduction to Algorithms Lecture 2 7 / 80

O-notation (upper bounds)

O(g(n)) = {f (n) : there exist constants

c > 0, n0 > 0 such that
0 ≤ f (n) ≤ cg(n)
for all n ≥ n0 }

Example
2n2 = O(n3 ) (c = 1, n0 = 2).

Functions,
not values! Funny, “one-way” equality...

Introduction to Algorithms Lecture 2 8 / 80

Set Definition of O-notation

O(g(n)) = {f (n) : there exist constants

c > 0, n0 > 0 such that
0 ≤ f (n) ≤ cg(n)
for all n ≥ n0 }

Introduction to Algorithms Lecture 2 9 / 80

Set Definition of O-notation

O(g(n)) = {f (n) : there exist constants

c > 0, n0 > 0 such that
0 ≤ f (n) ≤ cg(n)
for all n ≥ n0 }

Example:
2n2 ∈ O(n3 )

(Logicians: λn.2n2 ∈ O(λn.n3 ), but it’s convenient to be sloppy,

as long as we understand what’s really going on.)

Introduction to Algorithms Lecture 2 10 / 80

Macro substitution

Convention:
A set in a formula represents an anonymous function in the set.

Example:
f (n) = n3 + O(n2 )
means
f (n) = n3 + h(n)
for some h(n) ∈ O(n2 ).

Introduction to Algorithms Lecture 2 11 / 80

Macro substitution

Convention:
A set in a formula represents an anonymous function in the set.

Example:
n2 + O(n) = O(n2 )
means
for any f (n) ∈ O(n):
n2 + f (n) = h(n)
for some h(n) ∈ O(n2 ).

Introduction to Algorithms Lecture 2 12 / 80

Ω-notation (lower bounds)

O-notation is an upper-bound notation. It makes no sense

to say f (n) is at least O(n2 )

Introduction to Algorithms Lecture 2 13 / 80

 Ω-notation (lower bounds)

Ω(g(n)) = {f (n) : there exist constants

c > 0, n0 > 0 such that
0 ≤ cg(n) ≤ f (n)
for all n ≥ n0 }
4 Chapter 3 Characterizing Running Times

cg.n/ c2 g.n
f .n/
f .n/
f .n/
cg.n/
c1 g.n

n n n
n0 n0 n0
f .n/ D O.g.n// f .n/ D �.g.n// f .n/ D ‚.g.n//
(a) (b) (c)
Introduction to Algorithms Lecture 2 14 / 80
Ω-notation (lower bounds)

O-notation is an upper-bound notation. It makes no sense to

say f (n) is at least O(n2 )

Ω(g(n)) = {f (n) : there exist constants

c > 0, n0 > 0 such that
0 ≤ cg(n) ≤ f (n)
for all n ≥ n0 }

Example:
√
n = Ω(lg n) (c = 1, n0 = 16)

Introduction to Algorithms Lecture 2 15 / 80

 Θ-notation (tight bounds)

Θ(g(n)) = O(g(n)) ∩ Ω(g(n))

nning Times

c2 g.n/
f .n/
f .n/
cg.n/
c1 g.n/

n n
n0 n0
f .n/ D �.g.n// f .n/ D ‚.g.n//
(b) (c)

Introduction to Algorithms Lecture 2 16 / 80

Θ-notation (tight bounds)

Θ(g(n)) = O(g(n)) ∩ Ω(g(n))

Example:
1 2
2n − 2n = Θ(n2 )

Introduction to Algorithms Lecture 2 17 / 80

o-notation and ω-notation

O-notation and Ω-notation are like ≤ and ≥.

o-notation and ω-notation are like < and >.

o(g(n)) = {f (n) : for any constant c > 0,

there is a constant n0 > 0
such that 0 ≤ f (n) ≤ cg(n)
for all n ≥ n0 }

Example:
2n2 = o(n3 ) (n0 = 2c )

Introduction to Algorithms Lecture 2 18 / 80

o-notation and ω-notation

O-notation and Ω-notation are like ≤ and ≥.

o-notation and ω-notation are like < and >.

ω(g(n)) = {f (n) : for any constant c > 0,

there is a constant n0 > 0
such that 0 ≤ cg(n) ≤ f (n)
for all n ≥ n0 }

Example:
√
n = ω(lg n) (n0 = 1 + 1c )

Introduction to Algorithms Lecture 2 19 / 80

Plan

Asymptotic Notation

Solving recurrences
Substitution method
Recursion tree
The master method

Introduction to Algorithms Lecture 2 20 / 80

Solving recurrences

▶ The analysis of merge-sort from Lecture 1 required us to

solve a recurrence.
▶ Recurrences are like solving integrals, differential
equations, etc.
▶ Learn a few tricks.
▶ Lecture 3: Applications of recurrences to
divide-and-conquer algorithms.

Introduction to Algorithms Lecture 2 21 / 80

Substitution method

The method is based on guessing a possible solution and then

verifying it using mathematical induction. It is divided into the
following steps:
1. Guess a solution: Propose a general form of the solution
T (n), based on the structure of the problem.
2. Substitute into the recurrence: Replace the
conjectured solution in the recurrence equation to check if
it holds.
3. Adjust if necessary: If the conjecture is not valid,
modify it by adding constants or additional terms.
4. Prove by induction: Use mathematical induction to
demonstrate that the conjecture is correct.

Introduction to Algorithms Lecture 2 22 / 80

Substitution method

The most general method:

1. Guess the form of the solution.
2. Verify by induction.
3. Solve for constants.

Introduction to Algorithms Lecture 2 23 / 80

Substitution method

The most general method:

1. Guess the form of the solution.
2. Verify by induction.
3. Solve for constants.

Example:
T (n) = 4T ( n2 ) + n
▶ Assume that T (1) = Θ(1).
▶ Guess O(n3 ). (Prove O and Ω separately.)
▶ Assume that T (k) ≤ ck 3 for k < n.
▶ Prove T (n) ≤ cn3 by induction.

Introduction to Algorithms Lecture 2 24 / 80

Example of substitution

n
T (n) = 4T +n
2
 n 3
≤ 4c +n
 c 2
= n3 + n
2  
c 
= cn3 − n3 − n ←− desired − residual
2
≤ cn3 ←− desired
c
whenever n3 − n ≥ 0, for example, if c ≥ 2 and n ≥ 1.
2

residual

Introduction to Algorithms Lecture 2 25 / 80

Example (continued)

▶ We must also handle the initial conditions, that is, ground

the induction with base cases.
▶ Base: T (n) = Θ(1) for all n ≤ n0 , where n0 is a suitable
constant.
▶ For 1 ≤ n < n0 , we have “Θ(1)” ≤ cn3 , if we pick c big
enough.

Introduction to Algorithms Lecture 2 26 / 80

Example (continued)

▶ We must also handle the initial conditions, that is, ground

the induction with base cases.
▶ Base: T (n) = Θ(1) for all n ≤ n0 , where n0 is a suitable
constant.
▶ For 1 ≤ n < n0 , we have “Θ(1)” ≤ cn3 , if we pick c big
enough.

This bound is not tight!

Introduction to Algorithms Lecture 2 27 / 80

¿A tighter upper bound?

We shall prove that T (n) = O(n2 ).

Introduction to Algorithms Lecture 2 28 / 80

¿A tighter upper bound?

We shall prove that T (n) = O(n2 ).

Assume that T (k) ≤ ck 2 for k < n:

n
T (n) = 4T +n
2
 n 2
≤ 4c +n
2
= cn2 + n
= O(n2 )

Introduction to Algorithms Lecture 2 29 / 80

¿A tighter upper bound?

We shall prove that T (n) = O(n2 ).

Assume that T (k) ≤ ck 2 for k < n:

n
T (n) = 4T +n
2
 n 2
≤ 4c +n
2
= cn2 + n
= O(n2 ) Wrong! We must prove the I.H.

Introduction to Algorithms Lecture 2 30 / 80

¿A tighter upper bound?
We shall prove that T (n) = O(n2 ).

Assume that T (k) ≤ ck 2 for k < n:

n
T (n) = 4T +n
2
 n 2
≤ 4c +n
2
= cn2 + n
= O(n2 ) Wrong! We must prove the I.H.
= cn2 − (−n) [ desired − residual ]
≤ cn2 for no choice of c > 0. Lose!

Introduction to Algorithms Lecture 2 31 / 80

¡A tighter upper bound!

Idea:
▶ Strengthen the inductive hypothesis.
▶ Subtract a low-order term.
▶ Inductive hypothesis: T (k) ≤ c1 k 2 − c2 k for k < n.

Introduction to Algorithms Lecture 2 32 / 80

¡A tighter upper bound!
Idea:
▶ Strengthen the inductive hypothesis.
▶ Subtract a low-order term.
▶ Inductive hypothesis: T (k) ≤ c1 k 2 − c2 k for k < n.

n
T (n) = 4T +n
 2   n 
n 2
= 4 c1 − c2 +n
2 2
= c1 n2 − 2c2 n + n
= c1 n2 − c2 n − c2 n + n
= c1 n2 − c2 n − (c2 n − n)
≤ c1 n2 − c2 n if c2 ≥ 1.

Introduction to Algorithms Lecture 2 33 / 80

¡A tighter upper bound!
Idea:
▶ Strengthen the inductive hypothesis.
▶ Subtract a low-order term.
▶ Inductive hypothesis: T (k) ≤ c1 k 2 − c2 k for k < n.
n
T (n) = 4T +n
 2   n 
n 2
= 4 c1 − c1 +n
2 2
= c1 n2 − 2c2 n + n
= c1 n2 − c2 n − c2 n + n
= c1 n2 − c2 n − (c2 n − n)
≤ c1 n2 − c2 n if c2 ≥ 1.

Pick c1 big enough to handle the initial conditions.

Introduction to Algorithms Lecture 2 34 / 80
Recursion-tree method

▶ A recursion tree models the costs (time) of a recursive

execution of an algorithm.
▶ The recursion-tree method can be unreliable, just like any
method that uses ellipses (. . .).
▶ The recursion-tree method promotes intuition, however.
▶ The recursion-tree method is good for generating guesses
for the substitution method.

Introduction to Algorithms Lecture 2 35 / 80

Steps of the recurrence-tree method

1. Expand the recurrence over multiple levels until a

general pattern emerges.
2. Determine the cost at each level, which usually
depends on the number of subproblems and their size.
3. Calculate the depth of the tree, which is the total
number of levels until reaching base cases.
4. Sum the costs of all levels to obtain the overall cost.

Introduction to Algorithms Lecture 2 36 / 80

Example of recursion tree

n n
+ n2



Solve T (n) = T 4 +T 2

Introduction to Algorithms Lecture 2 37 / 80

Example of recursion tree
Example of recursion tree
SolveT (n)
T(n) = T(n/4)
n
+ n2 + n2:
4 + T +2 T(n/2)
n



Solve =T

T(n)

September 12, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.34

Introduction to Algorithms Lecture 2 38 / 80

Example of recursion tree
Example of recursion tree
SolveT (n)
T(n) = T(n/4)
n
+ n2 + n2:
4 + T +2 T(n/2)
n



Solve =T

n2
T(n/4) T(n/2)

September 12, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.35

Introduction to Algorithms Lecture 2 39 / 80

Example of recursion tree
Example of recursion tree
SolveT (n)
T(n) = T(n/4)
n
+ n2 + n2:
4 + T +2 T(n/2)
n



Solve =T

n2
(n/4)2 (n/2)2

T(n/16) T(n/8) T(n/8) T(n/4)

September 12, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.36

Introduction to Algorithms Lecture 2 40 / 80

Example of recursion tree
Example of recursion tree
SolveT (n)
T(n) = T(n/4)
n
+ n2 + n2:
4 + T +2 T(n/2)
n



Solve =T

n2
(n/4)2 (n/2)2

(n/16)2 (n/8)2 (n/8)2 (n/4)2

…

Θ(1)

September 12, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.37

Introduction to Algorithms Lecture 2 41 / 80

Example of recursion tree
Example of recursion tree
SolveT (n)
T(n) = T(n/4)
n
+ n2 + n2:
4 + T +2 T(n/2)
n



Solve =T

n2 n2
(n/4)2 (n/2)2

(n/16)2 (n/8)2 (n/8)2 (n/4)2

…

Θ(1)

September 12, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.38

Introduction to Algorithms Lecture 2 42 / 80

Example of recursion tree
Example of recursion tree
SolveT (n)
T(n) = T(n/4)
n
+ n2 + n2:
4 + T +2 T(n/2)
n



Solve =T

n2 n2
5 n2
(n/4)2 (n/2)2
16
(n/16)2 (n/8)2 (n/8)2 (n/4)2
…

Θ(1)

September 12, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.39

Introduction to Algorithms Lecture 2 43 / 80

Example of recursion tree
Example of recursion tree
SolveT (n)
T(n) = T(n/4)
n
+ n2 + n2:
4 + T +2 T(n/2)
n



Solve =T

n2 n2
5 n2
(n/4)2 (n/2)2
16
25 n 2
(n/16)2 (n/8)2 (n/8)2 (n/4)2
256

…
…

Θ(1)

September 12, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.40

Introduction to Algorithms Lecture 2 44 / 80

Example of recursion tree
Example of recursion tree
SolveT (n)
T(n) = T(n/4)
n
+ n2 + n2:
4 + T +2 T(n/2)
n



Solve =T

n2 n2
5 n2
(n/4)2 (n/2)2
16
25 n 2
(n/16)2 (n/8)2 (n/8)2 (n/4)2
256

…
…

Θ(1) Total = n 2 1 + 16 (
5 + (5 ) + (5 ) +L
16 16
2 3
)
= Θ(n2) geometric series
September 12, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.41

Introduction to Algorithms Lecture 2 45 / 80

The master method

The master method applies to recurrences of the form:

n
T (n) = aT + f (n),
b

You have a subproblems.

The master method

The master method applies to recurrences of the form:

n
T (n) = aT + f (n),
b

You have a subproblems.

n
Each of them is of size b.
The master method

The master method applies to recurrences of the form:

n
T (n) = aT + f (n),
b

You have a subproblems.

n
Each of them is of size b.

Then you’re doing f (n) nonrecursive work.

The master method

The master method applies to recurrences of the form:

n
T (n) = aT + f (n),
b

You have a subproblems.

n
Each of them is of size b.

Then you’re doing f (n) nonrecursive work.

Introduction to Algorithms Lecture 2 46 / 80

The master method

The master method applies to recurrences of the form:

n
T (n) = aT + f (n),
b
where a ≥ 1, b > 1, and f (n) is asymptotically positive.

Introduction to Algorithms Lecture 2 47 / 80

The master method

The master method applies to recurrences of the form:

n
T (n) = aT + f (n),
b
where a ≥ 1, b > 1, and f (n) is asymptotically positive.
Note
asymptotically positive means f (n) > 0 for n ≥ n0 .

Introduction to Algorithms Lecture 2 48 / 80

Three common cases

Compare f (n) with nlogb a :

Introduction to Algorithms Lecture 2 49 / 80

Three common cases

Compare f (n) with nlogb a :

Note:
nlogb a = The number of leaves in the recursion tree.

Introduction to Algorithms Lecture 2 49 / 80

Three common cases

Compare f (n) with nlogb a :

Note:
nlogb a = The number of leaves in the recursion tree.
Case 1 f (n) < nlogb a
Case 2 f (n) = nlogb a
Case 3 f (n) > nlogb a

Introduction to Algorithms Lecture 2 49 / 80

Three common cases
Compare f (n) with nlogb a :

Introduction to Algorithms Lecture 2 50 / 80

Three common cases
Compare f (n) with nlogb a :
1 f (n) = O nlogb a−ε for some constant ε > 0.

▶ f (n) grows polynomially slower than nlogb a (by an nε

factor, polynomially smaller).
▶ Solution:
T (n) = Θ(nlogb a ).

Introduction to Algorithms Lecture 2 50 / 80

Three common cases
Compare f (n) with nlogb a :
1 f (n) = O nlogb a−ε for some constant ε > 0.

▶ f (n) grows polynomially slower than nlogb a (by an nε

factor, polynomially smaller).
▶ Solution:
T (n) = Θ(nlogb a ).
2 f (n) = Θ(nlogb a lgk n) for some constant k ≥ 0.
▶ f (n) and nlogb a grow at similar rates, up to poly log factor.
▶ Solution:
T (n) = Θ(nlogb a lgk+1 n).

Introduction to Algorithms Lecture 2 50 / 80

Three common cases
Compare f (n) with nlogb a :
1 f (n) = O nlogb a−ε for some constant ε > 0.

▶ f (n) grows polynomially slower than nlogb a (by an nε

factor, polynomially smaller).
▶ Solution:
T (n) = Θ(nlogb a ).
2 f (n) = Θ(nlogb a lgk n) for some constant k ≥ 0.
▶ f (n) and nlogb a grow at similar rates, up to poly log factor.
▶ Solution:
T (n) = Θ(nlogb a lgk+1 n).
3 f (n) = Ω(nlogb a+ε ) for some constant ε > 0.
▶ f (n) grows polynomially faster than nlogb a (by an nε factor,
polynomially faster),
and f
(n) satisfies the regularity condition that
af nb ≤ cf (n) for some constant c < 1.
▶ Solution:
T (n) = Θ(f (n)).
Introduction to Algorithms Lecture 2 50 / 80
Examples

Ex. n
T (n) = 4T +n
2
a = 4, b = 2 =⇒ nlogb a = n2 ; f (n) = n.

Introduction to Algorithms Lecture 2 51 / 80

Examples

Ex. n
T (n) = 4T +n
2
a = 4, b = 2 =⇒ nlogb a = n2 ; f (n) = n.
Case 1:

Introduction to Algorithms Lecture 2 52 / 80

Examples

Ex. n
T (n) = 4T +n
2
a = 4, b = 2 =⇒ nlogb a = n2 ; f (n) = n.
Case 1:f (n) = O(n2−ε ) for ε = 1.

Introduction to Algorithms Lecture 2 53 / 80

Examples

Ex. n
T (n) = 4T +n
2
a = 4, b = 2 =⇒ nlogb a = n2 ; f (n) = n.
Case 1:f (n) = O(n2−ε ) for ε = 1.
∴ T (n) = Θ(n2 ).

Introduction to Algorithms Lecture 2 54 / 80

Examples

Ex. n
T (n) = 4T + n2
2

Introduction to Algorithms Lecture 2 55 / 80

Examples

Ex. n
T (n) = 4T + n2
2
a = 4, b = 2 =⇒ nlogb a = n2 ; f (n) = n2 .

Introduction to Algorithms Lecture 2 56 / 80

Examples

Ex. n
T (n) = 4T + n2
2
a = 4, b = 2 =⇒ nlogb a = n2 ; f (n) = n2 .
Case 2:

Introduction to Algorithms Lecture 2 57 / 80

Examples

Ex. n
T (n) = 4T + n2
2
a = 4, b = 2 =⇒ nlogb a = n2 ; f (n) = n2 .
Case 2:f (n) = Θ(n2 lg0 n), that is, k = 0.

Introduction to Algorithms Lecture 2 58 / 80

Examples

Ex. n
T (n) = 4T + n2
2
a = 4, b = 2 =⇒ nlogb a = n2 ; f (n) = n2 .
Case 2:f (n) = Θ(n2 lg0 n), that is, k = 0.
∴ T (n) = Θ(n2 lg n).

Introduction to Algorithms Lecture 2 59 / 80

Examples

Ex. n
T (n) = 4T + n3
2

Introduction to Algorithms Lecture 2 60 / 80

Examples

Ex. n
T (n) = 4T + n3
2
a = 4, b = 2 =⇒ nlogb a = n2 ; f (n) = n3 .

Introduction to Algorithms Lecture 2 61 / 80

Examples

Ex. n
T (n) = 4T + n3
2
a = 4, b = 2 =⇒ nlogb a = n2 ; f (n) = n3 .
Case 3:

Introduction to Algorithms Lecture 2 62 / 80

Examples

Ex. n
T (n) = 4T + n3
2
a = 4, b = 2 =⇒ nlogb a = n2 ; f (n) = n3 .
Case 3:f (n) = Ω(n2+ε ) for ε = 1.

Introduction to Algorithms Lecture 2 63 / 80

Examples

Ex. n
T (n) = 4T + n3
2
a = 4, b = 2 =⇒ nlogb a = n2 ; f (n) = n3 .
Case 3:f (n) = Ω(n2+ε ) for ε = 1.
 n 3 1
and 4 ≤ cn3 (reg. cond.) for c = .
2 2

Introduction to Algorithms Lecture 2 64 / 80

Examples

Ex. n
T (n) = 4T + n3
2
a = 4, b = 2 =⇒ nlogb a = n2 ; f (n) = n3 .
Case 3:f (n) = Ω(n2+ε ) for ε = 1.
 n 3 1
and 4 ≤ cn3 (reg. cond.) for c = .
2 2
∴ T (n) = Θ(n3 ).

Introduction to Algorithms Lecture 2 65 / 80

Examples

Ex.
n n2
T (n) = 4T +
2 lg n

Introduction to Algorithms Lecture 2 66 / 80

Examples

Ex.
n n2
T (n) = 4T +
2 lg n
n2
a = 4, b = 2 =⇒ nlogb a = n2 ; f (n) = .
lg n

Introduction to Algorithms Lecture 2 67 / 80

Examples

Ex.
n n2
T (n) = 4T +
2 lg n
n2
a = 4, b = 2 =⇒ nlogb a = n2 ; f (n) = .
lg n
2
▶ f (n) = lgn n . Have f (n) = o(n), so that f (n) grows more slowly
than n, it doesn’t grow polynomially slower.
▶ In terms of the master theorem, have f (n) = n2 lg−1 n, so that
k = −1.
▶ Master theorem holds only for k ≥ 0, so case 2 does not apply.
▶ Master method does not apply.

Introduction to Algorithms Lecture 2 68 / 80

Intuition behind of master theorem
Idea of master theorem
Recursion tree:
Recursion tree:
a f (n)
f (n/b) f (n/b) … f (n/b)
a
f (n/b2) f (n/b2) … f (n/b2)
…

Τ (1)

September 12, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.50

Introduction to Algorithms Lecture 2 69 / 80

Intuition behind of master theorem
Idea of master theorem
Recursion tree:
Recursion tree:
f (n) f (n)
a
f (n/b) f (n/b) … f (n/b) a f (n/b)
a
f (n/b2) f (n/b2) … f (n/b2) a2 f (n/b2)
…

…
Τ (1)

September 12, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.51

Introduction to Algorithms Lecture 2 70 / 80

Intuition behind of master theorem
Idea of master theorem
Recursion tree:
Recursion tree:
f (n) f (n)
a
f (n/b) f (n/b) … f (n/b) a f (n/b)
h = logbn a
f (n/b2) f (n/b2) … f (n/b2) a2 f (n/b2)
…

…
Τ (1)

September 12, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.52

Introduction to Algorithms Lecture 2 71 / 80

Intuition behind of master theorem
Idea of master theorem
Recursion tree:
Recursion tree:
f (n) f (n)
a
f (n/b) f (n/b) … f (n/b) a f (n/b)
h = logbn a
f (n/b2) f (n/b2) … f (n/b2) a2 f (n/b2)

#leaves = ah
…

…
= alogbn
Τ (1) nlogbaΤ (1)
= nlogba

September 12, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.53

Introduction to Algorithms Lecture 2 72 / 80

Intuition behind of master theorem
Idea of master theorem
Recursion tree:
Recursion tree:
f (n) f (n)
a
f (n/b) f (n/b) … f (n/b) a f (n/b)
h = logbn a
f (n/b2) f (n/b2) … f (n/b2) a2 f (n/b2)
…

C ASE 1:
1: The
The weight
weight increases

…
CASE increases
geometrically
geometrically from the root
from the root to
to the
the
Τ (1) leaves. The leaves hold a constant
leaves. The leaves hold a constant nlogbaΤ (1)
fraction
fraction of
of the
the total
total weight.
weight.
Θ(nlogba)
September 12, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.54

Introduction to Algorithms Lecture 2 73 / 80

Intuition behind of master theorem
Idea of master theorem
Recursion tree:
Recursion tree:
f (n) f (n)
a
f (n/b) f (n/b) … f (n/b) a f (n/b)
h = logbn a
f (n/b2) f (n/b2) … f (n/b2) a2 f (n/b2)
…

…
CCASEASE 2:
2: (k
(k == 0)
0) The
The weight
weight
Τ (1) isis approximately
approximately the the same
same on
on nlogbaΤ (1)
each of the log n levels.
each of the logbbn levels.
Θ(nlogbalg n)
September 12, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.55

Introduction to Algorithms Lecture 2 74 / 80

Intuition behind of master theorem
Idea of master theorem
Recursion tree:
Recursion tree:
f (n) f (n)
a
f (n/b) f (n/b) … f (n/b) a f (n/b)
h = logbn a
f (n/b2) f (n/b2) … f (n/b2) a2 f (n/b2)
…

C ASE 3:
3: The
The weight
weight decreases

…
CASE decreases
geometrically
geometrically from the root
from the root to
to the
the
Τ (1) leaves. The root holds a constant
leaves. The root holds a constant nlogbaΤ (1)
fraction
fraction of
of the
the total
total weight.
weight.
Θ( f (n))
September 12, 2005 Copyright © 2001-5 Erik D. Demaine and Charles E. Leiserson L2.56

Introduction to Algorithms Lecture 2 75 / 80

Appendix: geometric series

1 − xn+a
1 + x + x2 + · · · + xn = for x ̸= 1
1−x
1
1 + x + x2 + · · · = for |x| < 1
1−x

Introduction to Algorithms Lecture 2 76 / 80

 End of Lecture 2.

Introduction to Algorithms Lecture 2 77 / 80

TDT5FTOTC

Introduction to Algorithms Lecture 2 78 / 80

Top 5 Fundamental Takeaways

Introduction to Algorithms Lecture 2 79 / 80

Top 5 Fundamental Takeaways
5 Solving Recurrences: Common methods to solve recurrences
include substitution, recursion trees, and the master theorem,
each providing different approaches to analyze recursive
complexity.

Introduction to Algorithms Lecture 2 79 / 80

Top 5 Fundamental Takeaways
5 Solving Recurrences: Common methods to solve recurrences
include substitution, recursion trees, and the master theorem,
each providing different approaches to analyze recursive
complexity.
4 Tightening Bounds Using Substitution: Strengthening
inductive hypotheses by subtracting lower-order terms helps
refine bounds when standard methods provide loose
approximations.

Introduction to Algorithms Lecture 2 79 / 80

Top 5 Fundamental Takeaways
5 Solving Recurrences: Common methods to solve recurrences
include substitution, recursion trees, and the master theorem,
each providing different approaches to analyze recursive
complexity.
4 Tightening Bounds Using Substitution: Strengthening
inductive hypotheses by subtracting lower-order terms helps
refine bounds when standard methods provide loose
approximations.
3 Recursion Tree Intuition: A recursion tree models the
breakdown of recursive calls, where the total complexity is
derived by summing work across all levels.

Introduction to Algorithms Lecture 2 79 / 80

Top 5 Fundamental Takeaways
5 Solving Recurrences: Common methods to solve recurrences
include substitution, recursion trees, and the master theorem,
each providing different approaches to analyze recursive
complexity.
4 Tightening Bounds Using Substitution: Strengthening
inductive hypotheses by subtracting lower-order terms helps
refine bounds when standard methods provide loose
approximations.
3 Recursion Tree Intuition: A recursion tree models the
breakdown of recursive calls, where the total complexity is
derived by summing work across all levels.
2 Master Theorem Cases: The master theorem classifies
recurrences into three cases based on how f (n) compares to
nlogb (a) , determining whether recursion, work per level, or
additional growth dominates.

Introduction to Algorithms Lecture 2 79 / 80

Top 5 Fundamental Takeaways
5 Solving Recurrences: Common methods to solve recurrences
include substitution, recursion trees, and the master theorem,
each providing different approaches to analyze recursive
complexity.
4 Tightening Bounds Using Substitution: Strengthening
inductive hypotheses by subtracting lower-order terms helps
refine bounds when standard methods provide loose
approximations.
3 Recursion Tree Intuition: A recursion tree models the
breakdown of recursive calls, where the total complexity is
derived by summing work across all levels.
2 Master Theorem Cases: The master theorem classifies
recurrences into three cases based on how f (n) compares to
nlogb (a) , determining whether recursion, work per level, or
additional growth dominates.
1 O, Ω, and Θ notations describe upper, lower, and tight bounds
on algorithm growth (o and ω represent strict bounds).
Introduction to Algorithms Lecture 2 79 / 80
Introduction to Algorithms

Content has been extracted from Introduction to Algorithms, Fourth Edition, by Cormen,
Leiserson, Rivest, and Stein. MIT Press. 2022.
Visit [Link]
Original slides from Introduction to Algorithms 6.046J/18.401J, Fall 2005 Class by Prof. Charles
Leiserson and Prof. Erik Demaine. MIT OpenCourseWare Initiative available at
[Link]

Introduction to Algorithms Lecture 2 80 / 80