SECTION [4]

Nagwa Mohamed
AGENDA
• MASTER METHOD
• ITERATION METHOD
• Recursion Tree
• Substitution method
SOLVING RECURRENCE EQUATION

1. Master method
2. Iteration method
3. Recursion Tree
4. Substitution method
 MASTER METHOD
We use the master theorem to solve recurrence relations with the following format:-

T(n)=a T(n/b)+f(n)
Let a >=1 and b >= 1 be constants,
let f(n) be a nonnegative function,
and let T(n) be defined on the nonnegative integers by the recurrence
To use the master method, you will need to memorize three cases
 MASTER METHOD

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

Same as previous cases but in another form

 MASTER METHOD

EX.1 𝑇 (𝑛) = 2𝑇 (𝑛 /2) + 𝑛

• 𝒂=𝟐,

• 𝒃=𝟐

• 𝒇( 𝒏) = 𝒏

• .

T(n) =O( n log n)

 MASTER METHOD

EX.2 T(n) = 9T(n/3) + n

• 𝒂=9,

• 𝒃=3

• 𝒇( 𝒏) = 𝒏

• .
 MASTER METHOD

EX.3 T(n)= T(2n/3)+ 1

• 𝒂=1,

• 𝒃 = 3/2

• 𝒇( 𝒏) = 1

• .
 MASTER METHOD

EX.4 𝑇(𝑛) = 𝑇( 𝑛/2 )+ 𝑛

• 𝒂=1,

• 𝒃=2

• 𝒇( 𝒏) = n

• .

T(n)= Θ(n)
 ITERATION METHOD

The iteration method

is a "brute force" method of solving a recurrence
relation. The general idea is to iteratively substitute the value
of the recurrent part of the equation until a pattern (usually a
summation) is noticed, at which point the summation can be
used to evaluate the recurrence
 ITERATION METHOD

EX.1 𝑇 (𝑛) = 𝑇 (𝑛 /2) + c

 ITERATION METHOD

EX.1 𝑇 (𝑛) = 𝑇 (𝑛 /2) + c

Note T(1) is the base
case. So, we have
reached the base
case.
 ITERATION METHOD

EX.2 𝑇 (𝑛) = 𝑇 (𝑛 -1) + c

Iteration 1: T(n) = T(n-1) + c = T(n-1) + 1c

Iteration 2: T(n)=T(n-1-1)+c+c =T(n-2)+2c
Iteration 3: T(n)=T(n-2-1)+c+2c=T(n-3)+3c
Iteration 4: T(n)=T(n-3-1)+c+3c=T(n-4)+4c

T(n) = T(n-k)+kc Note T(1) is the base case. So, we have reached the base case.

n-k=1
K=n-1
T(n)=T(1)+c(n-1) =O(n)
 ITERATION METHOD

EX.3 𝑇 (𝑛) = 2𝑇(𝑛/2) + n

Iteration 1: T(n) = 2𝑇(𝑛/2) + n
Iteration 2: T(n)=2[2T(n/4)+n/2]+n = 4T(n/4)+2n
Iteration 3: T(n)=4[2T(n/8)+n/4]+2n=8T(n/8)+3n

NoteT(1) is the base case. So, we have reached the base case.

.
. O(n log n)
 ITERATION METHOD

EX.4 T(n)=T(n-1)+n
𝑇 (𝑛) = 𝑇 (𝑛) = 𝑇 (𝑛 -1) + n
Iteration 1: T(n) = 𝑇(𝑛 -1) + n
Iteration 2: T(n)=T(n-1-1)+(n-1)+n =T(n-2)+(n-1)+n
Iteration 3: T(n)=T(n-2-1)+(n-2)+(n-1)+n=T(n-3)+(n-2)+(n-1)+n
Iteration 4: T(n)=T(n-3-1)+(n-3)+(n-2)+(n-1)+n=T(n-4)+(n-3)+(n-2)+(n-1)+n

We find this pattern

 ITERATION METHOD
𝑛
EX.5 T 𝑛 = 4𝑇
2
+ 𝑛2

𝑛
Iteration 1: T(n) = 4𝑇 + 𝑛2
2
𝑛2 𝑛 2 𝑛 2 2 𝑛
Iteration 2: T(n)= 4[4𝑇 + ] + 𝑛 = 16 𝑇 + 𝑛 +𝑛 =16 𝑇 + 2𝑛2
4 4 4 4
𝑛2𝑛 2 𝑛 2 2 𝑛
Iteration 3: T(n)=16[4𝑇 + ] + 2𝑛 = 64 𝑇 + 𝑛 +2𝑛 =64 𝑇 + 3𝑛2
16 8 8 8
𝑛 𝑛2 𝑛 𝑛
Iteration 4: T(n)=T(n)=64[4𝑇 16 + 64 ] + 3𝑛2 = 256 𝑇
16
+ 𝑛2 +3𝑛2 =256 𝑇
16
+ 4𝑛2
We find this pattern
𝑛
𝑇 𝑛 = 4𝑘 𝑇 + 𝑘𝑛 2
2𝑘
𝑛 𝑙𝑜𝑔 𝑛 2 𝑙𝑜𝑔 22
𝑘 =1  k =𝑙𝑜𝑔2 𝑛 𝑇 𝑛 =4 2 T 1 + 𝑙𝑜𝑔2 𝑛 𝑛 =𝑛 2 + 𝑛2 𝑙𝑜𝑔2 𝑛
2
𝑇 𝑛 = 2𝑛 + 𝑛2 𝑙𝑜𝑔2 𝑛=O(𝑛2 𝑙𝑜𝑔2 𝑛)
 RECURSION TREE

• in a recursion tree, each node represents the cost of a

single subproblem somewhere in the set of recursive
function invocations.
1. We sum the costs within each level of the tree to obtain a
set of per-level costs,
2. and then we sum all the per-level costs to determine the
total cost of all levels of the recursion.
 RECURSION TREE
EX.1 𝑇(𝑛) = 2𝑇(𝑛/3) +𝑛

𝑇(𝑛/3) = 2𝑇(𝑛/9) +𝑛/3

𝑛
𝑡( ) 𝑛
3 𝑡( )
3
 RECURSION TREE
EX.1 𝑇(𝑛) = 2𝑇(𝑛/3) +𝑛

𝑇(𝑛/9) = 2𝑇(𝑛/27) +𝑛/9

𝑛
𝑛
3
3

𝑛 𝑛 𝑛 𝑛
𝑡( ) 𝑡( ) 𝑡( ) 𝑡( )
9 9 9 9
 RECURSION TREE
EX.1 𝑇(𝑛) = 2𝑇(𝑛/3) +𝑛

𝑛
𝑛
3
3

𝑛 𝑛 𝑛 𝑛
9 9 9 9

𝑛 𝑛 𝑛 𝑛 𝑛 𝑛 𝑛 𝑛
𝑡( ) 𝑡( ) 𝑡( ) 𝑡( ) 𝑡( ) 𝑡( ) 𝑡( ) 𝑡( )
27 27 27 27 27 27 27 27
 RECURSION TREE
EX.1 𝑇(𝑛) = 2𝑇(𝑛/3) +𝑛
Level 0
n n

𝑛
𝑛 Level 1 2𝑛
3
3
3
h=𝑙𝑜𝑔3 𝑛

4𝑛 22 𝑛
𝑛 𝑛 𝑛 𝑛 Level 2 = 32
9
9 9 9 9

𝑛 𝑛 𝑛 𝑛 𝑛 𝑛 𝑛 𝑛 Level 3 8𝑛 23 𝑛
𝑡( ) 𝑡( ) 𝑡( ) 𝑡( ) 𝑡( ) 𝑡( ) 𝑡( ) 𝑡( ) =
27 27 27 27 27 27 27 27 27 33

. . . . . . . .
. . . . . . . . 2𝑘 𝑛
T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) Level k=h=𝑙𝑜𝑔3 𝑛 3𝑘
 RECURSION TREE
EX.1 𝑇(𝑛) = 2𝑇(𝑛/3) +𝑛

2 2 2 2
Sum of all levels = n + ( )1 n +( )2 n +( )3 n +…+( )𝑘 n
3 3 3 3

2 1 2 2 2 3 2 𝑙𝑜𝑔 𝑛
=n[ ( ) +( ) +( ) +…+( ) 3 ]  geometric series
3 3 3 3
𝑙𝑜𝑔3 𝑛
2 𝑖 1
𝑛 ෍ ( ) = 𝑛.
3 2
𝑖=1 1 −
3
𝒕 𝒏 = 𝑶(𝒏)
 RECURSION TREE
EX.2 𝑇(𝑛) = 2𝑇(𝑛/2) +c
Level 0
c C

𝑛 𝑛
𝑡[ ] 𝑡[ ]
2 𝑐 2 Level 1 2𝑐
c
h=𝑙𝑜𝑔2 𝑛

𝑛 𝑛
𝑡[ ] 𝑛 𝑛
4 𝑡[ ] 𝑡[ ] 𝑡[ ]
4 4 4 Level 2
c c 4𝑐
c c

𝑛 𝑛 𝑛 𝑛 𝑛 𝑛 𝑛 𝑛 Level 3 8𝑐
𝑡( ) 𝑡( ) 𝑡( ) 𝑡( ) 𝑡( ) 𝑡( ) 𝑡( ) 𝑡( )
8 8 8 8 8 8 8 8
. . . . . . . .
. . . . . . . . k
T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) Level k=h=𝑙𝑜𝑔2 𝑛 k𝑐c
2
 RECURSION TREE
EX.2 𝑇(𝑛) = 2𝑇(𝑛/3) +𝑛
EX.2 T(n)=2T(n/2)+c

Sum of all levels = c +2c +4c +8c +…2 kc

= c [1+2+4+8 +…𝑙𝑜𝑔
2 3 𝑛 ]  geometric series
𝑙𝑜𝑔3 𝑛
1 − 2 𝑙𝑜𝑔2 𝑛 1 − 𝑛 𝑙𝑜𝑔2 2 1−𝑛
𝑖
𝑐 ෍ (2) = 𝑐 . = 𝑐. = 𝑐.
1−2 1−2 1−2
𝑖=1

𝒕 𝒏 = 𝑶(𝒏)
 RECURSION TREE
EX.3 𝑇(𝑛) =𝑇(𝑛/4)+𝑇(𝑛/2) +𝑛2
Level 0
𝑛2 𝑛2

𝑛 𝑛
𝑡[ ] 𝑛 𝑡[ ]
4 ( )2 2 𝑛 Level 1 5 1 2
4 ( )2 ( ) 𝑛
2 16
h=𝑙𝑜𝑔2 𝑛

𝑛 𝑛 𝑛
𝑡[ ] 𝑡[ ] 𝑛
16 𝑡[ ] 𝑡[ ]
8 8 4
𝑛 2 𝑛 𝑛 𝑛 Level 2 5 2 2
( ) ( )2 ( )2 ( )2 ( ) 𝑛
16 8 8 4 16

𝑛 𝑛 𝑛 𝑛 𝑛 𝑛 𝑛 𝑛 Level 3 5 3 2
𝑡(
64
) 𝑡( ) 𝑡(
32
) 𝑡( ) 𝑡( ) 𝑡( ) 𝑡( ) 𝑡( ) ( ) 𝑛
32 16 32 16 16 8 16
. . . . . . . .
. . . . . . . . 5 𝑘 2
T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) Level k=h=𝑙𝑜𝑔2 𝑛 ( ) 𝑛
16
 RECURSION TREE

EX.3 T(n/4)+T(n/2)+n2
EX.3 𝑇(𝑛) = 2𝑇(𝑛/3) +𝑛

5 5 5 5
Sum of all levels =𝑛2 + ( )1 𝑛2 +( )2 𝑛2 + ( )3 𝑛2 +….+( )𝑘 𝑛2
16 16 16 16
2 5 1 5 2 5 3 5 𝑙𝑜𝑔 𝑛
= 𝑛 [( ) +( ) +( ) … ( ) 2 ]  geometric series
16 16 16 16
𝑙𝑜𝑔2 𝑛
5 1
𝑛2 ෍ ( )𝑖 = 𝑛2 .
16 5
𝑖=1 1 −
16
𝒕 𝒏 = 𝑶( 𝒏𝟐 )
 RECURSION TREE
EX.4 𝑇(𝑛) = t(n−1)+t(n−2)+1
Level 0
1 1

𝑡(𝑛 − 1) 𝑡(𝑛 − 2)
1 Level 1 2 → 21
1

𝑡(𝑛 − 1)
2
h=𝑛

𝑡(𝑛 − 32) 𝑡(𝑛 − 31) 𝑡(𝑛 − 42)

1
Level 2 4 → 22
1 1 1

Level 3
𝒕(𝒏 − 3𝟏) 𝒕(𝒏 −4𝟐) 𝒕(𝒏 −4𝟏) 𝒕(𝒏 − 5
𝟐) 𝒕(𝒏 − 4𝟏) 𝒕(𝒏 −5𝟐) 𝒕(𝒏 − 5
𝟏) 𝒕(𝒏 −6𝟐) 8 → 23

. . . . . . . .
. . . . . . . .
T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) Level k=h=𝑛 2𝑘
 RECURSION TREE
EX.4 𝑇(𝑛) = t(n−1)+t(n−2)+1

Sum of all levels = 1+2+4+8+ …+ k= 1+2+4+8+ …+ n  geometric series

𝑛
𝑛
1 − 2
෍(2)𝑖 =
1−2
𝑖=1

𝒕 𝒏 = 𝑶(𝟐^𝒏)
 RECURSION TREE
EX.5 𝑇(𝑛) = t(n−1)+n
Level 0
n n

Level 1
𝑡(𝑛 − 1) n-1 𝑛−1
h=𝑛

Level 2
𝑡(𝑛 − 2) n-2 𝑛−2

Level 3
n-3 𝑛−3
𝑡(𝑛 − 3)
.
. Level k=h=𝑛
T(1) 𝑛−𝑘
 RECURSION TREE
EX.5 𝑇(𝑛) = t(n−1)+t(n−2)+1
2
EX.5 T(n)=T(n-1)+n

Sum of all levels = n+n-1+n-2 +n-3+ …+ n-k=  arithmetic series

𝑛 𝑛(𝑛+1)
T(n) =σ𝑖=1 𝑖 =
2

𝒕 𝒏 = 𝑶(𝒏^𝟐)
 RECURSION TREE
1
EX.6 𝑇(𝑛) = t(n−1)+
𝑛 Level 0
1/n 1/n

𝟏 Level 1 1
𝑡(𝑛 − 1) 𝒏−𝟏
𝑛−1
h=𝑛

𝟏 Level 2 1
𝑡(𝑛 − 2) 𝒏−𝟐 𝑛−2

𝟏 Level 3 1
𝑡(𝑛 − 3)
𝒏−𝟑 𝑛−3
.
. Level k=h=𝑛 1
T(1) 𝑛−𝑘
 RECURSION TREE
EX.6 𝑇(𝑛) = t(n−1)+t(n−2)+1
Ex.6 T(n)=T(n-1)+1/n

1/ 1 1 1 1
Sum of all levels = n+ + + +… +  ℎ𝑎𝑟𝑚𝑜𝑛𝑖𝑐 𝑠𝑒𝑟𝑖𝑒𝑠
𝑛−1 𝑛−2 𝑛−3 𝑛−𝑘
1
T(n) =σ𝑛𝑖=1 = ln 𝑛 + 1
𝑖

𝒕 𝒏 = 𝑶(𝒍𝒏 𝒏)
 SUBSTITUTION METHOD

The substitution method for solving recurrence relations consists of

three steps:-
1. Guess the form of the solution.
2. Verify by induction.
3. Solve for constants.
 SUBSTITUTION METHOD
EX.1 𝑇(𝑛) =2𝑇(𝑛/2)+n
1. Guess : 𝑇(𝑛) = O(n 𝑙𝑜𝑔2 n)
𝑇(𝑛) ≤ c.n 𝑙𝑜𝑔2 n
𝑇(n/2) ≤ c. n/2 𝑙𝑜𝑔2 n/2

𝑛 𝑛
2. Verify: 𝑇(n) ≤ 2 c. 2 𝑙𝑜𝑔2 2 +n
𝑛
𝑇(n) ≤ c. n 𝑙𝑜𝑔2 2 +n
𝑇(n) ≤ c. n (𝑙𝑜𝑔2 𝑛 − 𝑙𝑜𝑔2 2)+n
𝑇(n) ≤ c. n (𝑙𝑜𝑔2 𝑛 − 1)+n
𝑇(n) ≤ c. n 𝑙𝑜𝑔2 𝑛 − 𝑐𝑛 +n
𝑇(n) ≤ c. n 𝑙𝑜𝑔2 𝑛 − 𝑛 (𝑐 − 1)
𝑇(n) ≤ c. n 𝑙𝑜𝑔2 𝑛
𝑇(n) = 𝑂(n 𝑙𝑜𝑔2 𝑛)
3. Solve for constants
𝑐−1≥0⇒𝑐≥1
 GEOMETRIC SERIES REVIEW
finite geometric series the common ratio (r) is greater than 1
a1 + ar + ar^2 + ar^3 + ... + ar^(n-1) + ...
To find the sum of a finite geometric series, use the formula

infinite geometric series absolute value of the common ratio (|r|) is strictly less than 1
a1 + ar + ar^2 + ar^3 + ...
To find the sum of a finite geometric series, use the formula