Course Information

Dr. Mohammed N. M. Ali

Design and Analysis of Algorithms School of Computer Science and Technology, Xiamen University
• [email protected]
Lecture (7) - week (4) • Office: A1-363
September Intake 2023 • Consultation hours:
✓Tuesday 12 PM – 2 PM
✓Wednesday 11 AM – 1 PM
1
 Chapter 3 (ii)

Recurrences
 Agenda
Recursion tree method
Examples
Master Method
Examples.
 Recursion-tree method
 A recursion tree models the costs (time) of a recursive
execution of an algorithm.
 The recursion tree method is good for generating
guesses for the substitution method.
 The recursion-tree method can be unreliable, just like
any method that uses ellipses.
 The recursion-tree method promotes intuition,
however.
 Recursion-tree method
 A recursion tree is useful for visualizing what happens when a
recurrence is iterated.
 It diagrams the tree of recursive calls and the amount of work
done at each call.
 The recursion tree method is used to solve recurrence relations.
 For example, 𝑻(𝒏) = 𝑻(𝒏 − 𝟏) + 𝑻(𝒏 − 𝟐) + 𝒌, is a
recurrence relation as problem size ′𝑛′ is dividing into sub-
problems of size 𝒏 − 𝟏 and 𝒏 − 𝟐. can be solved with recursion
tree method.
 Recursion-tree method
 Recursion Tree Method is a pictorial representation of an
iteration method which is in the form of a tree where at each
level nodes are expanded.
 In general, we consider the second term in recurrence as the
root.
 It is useful when the divide & Conquer algorithm is used.
 It is sometimes difficult to produce a good guess.
 We sum the costs within each of the levels of the tree to obtain
a set of pre-level costs and then sum all pre-level costs to
determine the total cost of all levels of the recursion.
 Recursion-tree method
 A recursion tree is a tree where each node represents the cost of a
certain recursive subproblem.
 Note: We would usually use a recursion tree to generate possible
guesses for the runtime, and then use the substitution method to prove
them.
 However, if you are very careful when drawing out a recursion tree and
summing the costs, you can use a recursion tree as direct proof of a
solution to a recurrence.
 If we are only using recursion trees to generate guesses and not prove
anything, we can tolerate a certain amount of “sloppiness” in our
analysis. For example, we can ignore floors and ceilings when solving our
recurrences, as they usually do not affect the final guess.
 Steps to Solve Recurrence Relations Using
Recursion Tree Method
 To solve a recurrence relation using the recursion tree
method, a few steps must be followed. They are,
1. Draw the recursion tree for the given recurrence relation.
2. Calculate the height of the recursion tree formed.
3. Calculate the cost(time required to solve all the subproblems
at a level) at each level.
4. Calculate the total number of nodes at each level in the
recursion tree.
5. Sum up the cost of all the levels in the recursion tree.
 Let's understand all these steps with a few examples.
Recurrence Relations Using Recursion Tree Method
𝒏
𝑻 𝒏 = 𝒂𝑻 + 𝒄𝒏
𝒃
Problem Size The local TC at the node

Number of subproblems => Size of a subproblem =>

Number of children of a node Affects the number of recursive
calls (frame stack max height and
in the recursion tree. =>
tree height)
Affects the number of nodes Recursion stops at level 𝑘 for which
per level. At level 𝑖 there will the problem size is 1 (the node is
be 𝑎 𝑖 nodes. labelled
Affects the level TC T(1) ) => 𝑛/𝑏 𝑘 = 1 =>
Last level, 𝑘, will be: 𝑘 = 𝑙𝑜𝑔𝑏 𝑛
(assuming the base case is for T(1) ).
Base case: T(1) = c
TC= Time complexity
 𝒏
Example 1: 𝑻 𝒏 = 𝟐𝑻 + 𝒄𝒏
𝟐

 Step-01: Draw a recursion tree based on the given recurrence

relation.
 The given recurrence relation shows
→ A problem of size 𝑛 will get divided into 2 sub-problems both
of size 𝑛/2.
→ Then, sub-problem of size 𝑛/2 will get divided into 2 sub-
problems- both of size n/4.
→ At the bottom most layer, the size of sub-problems will
reduce to 1.
 This is illustrated through following recursion tree.
 Example 1: Solution
n
T n = 2T + cn
2
𝑛 𝑛
𝑇 = 2𝑇 + 𝑐𝑛/2
2 4
𝑛 𝑛
𝑇 = 2𝑇 + 𝑐𝑛/4
T(n) Level-0 4 8
cn Level-0

T(n/2) T(n/2) Level-1 cn/2 cn/2 Level-1

T(n/4) T(n/4) Level-2

T(n/4) T(n/4) Level-2 cn/4 cn/4 cn/4 cn/4

K-Level
T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) K-Level
 Step-02:
 Determine cost of each level:
→ Cost of level-0 = 𝑐𝑛
𝑐𝑛 𝑐𝑛
→ Cost of level-1 = + = 𝑐𝑛
2 2
𝑐𝑛 𝑐𝑛 𝑐𝑛 𝑐𝑛
→ Cost of level-2 = + + + = 𝑐𝑛, and so on.
4 4 4 4
 Step-03:
 Determine total number of levels in the recursion tree-
𝑐𝑛
→ Size of sub-problem at level-0 =
20
𝑐𝑛
→ Size of sub-problem at level-1 =
21
𝑐𝑛
→ Size of sub-problem at level-2 =
22
 Continuing in similar manner, we have-
𝑐𝑛
→ Size of sub-problem at level-i =
2𝑖
 Suppose at level-k (last level), size of sub-problem becomes 1. Then-
𝑐𝑛
→ =1
2𝑘
𝑘
→2 = 𝑐𝑛
 Taking log on both sides, we get:
→ 𝑙𝑜𝑔2𝑘 = 𝑐𝑙𝑜𝑔𝑛
→ 𝑘 = 𝑐𝑙𝑜𝑔2𝑛 Total number of levels in the recursion tree = log2n + 1 (+1 because we start counting from level 0)
Step-04:
Determine number of nodes in the last level-
→Level-0 has 20 nodes i.e., 1 node
→Level-1 has 21 nodes i.e., 2 nodes
→Level-2 has 22 nodes i.e., 4 nodes
Continuing in similar manner, we have-
→Level-log2𝑛 has 2𝑙𝑜𝑔2 𝑛 nodes i.e., 𝑛 nodes

Step-05:
Determine cost of last level: Base case: T(1) = c
→Cost of last level = 𝑛 × 𝑇 1 = 𝜃(𝑛)
Step-06:
→Add costs of all the levels of the recursion tree and simplify the expression so
obtained in terms of asymptotic notation:

𝑻 𝒏 = 𝒄𝒏 + 𝒄𝒏 + 𝒄𝒏 + ⋯ + 𝜣(𝒏)

For 𝑙𝑜𝑔𝑛 levels

= 𝑐𝑛 × log2𝑛 + 𝜃 (𝑛)
= 𝑐𝑛𝑙𝑜𝑔2𝑛 + 𝜃 (𝑛)
= 𝜽 (𝒏𝒍𝒐𝒈𝟐𝒏)
 𝒏
Example 1: 𝑻 𝒏 = 𝟐𝑻 + 𝒄𝒏 (Method 2)
𝟐

Level Problem TC of 1 Nodes per Level TC

Size node level
𝑇(𝑛)
𝑐𝑛 0 𝑛 𝑐𝑛 1 𝑐𝑛
𝑛 𝐶𝑛 1 𝑛 𝑐𝑛 2 𝑐𝑛
𝑛 𝑇( ) 2×
𝐶𝑛 𝑇( ) 2 2 2
2 2 2
2 = 𝑐𝑛
2 𝑛 𝑐𝑛 4 𝑐𝑛
𝑛 𝑛 4×
𝑇( ) 𝑛 𝑛 𝐶𝑛 4 4 4
4 𝐶𝑛 𝑇( ) 𝐶𝑛 𝑇( ) 𝐶𝑛 𝑇( ) = 𝑐𝑛
4 4 4 4 4
4 4 𝑖 𝑛 𝑐𝑛 2𝑖 𝑖
𝑐𝑛
2 × 𝑖
2𝑖 2𝑖 2
…………………………………………………….. = 𝑐𝑛
𝑇(1) 𝑇(1) 𝑇(1) 𝑇(1) ……..

c c ………………………….. c c 𝐾 = 𝑙𝑜𝑔𝑛 𝑛 𝑐 =𝑐×1 2𝑘 = 𝑛 𝑐𝑛

1=(2𝑘) 𝑐𝑛 2𝑘 ×
= 𝑘 2𝑘
2 = 𝑐𝑛
Stop at level k, when the subtree is T(1). => The problem size is 1, but the
general formula for the problem size, at level k is: Tree TC = 𝑐𝑛 (k + 1) = 𝑐𝑛 (1 + 𝑙𝑔𝑛)
𝑛 𝑛
𝑘 ⇒ 𝑘 = 1 ⇒ 2 𝑘
= n ⇒ k = logn = 𝑐𝑛𝑙𝑔𝑛 + 𝑐𝑛 = 𝜃(𝑛𝑙𝑔𝑛)
2 2
 Example: Solve the following recurrence relation using recursion tree method:
T(n) = T(n/5) + T(4n/5) + n

Step-01:
Draw a recursion tree based on the given recurrence relation.
The given recurrence relation shows:
→A problem of size n will get divided into 2 sub-problems- one of size n/5 and
another of size 4n/5.
→Then, sub-problem of size n/5 will get divided into 2 sub-problems- one of size
n/52 and another of size 4n/52.
→On the other side, sub-problem of size 4n/5 will get divided into 2 sub-
problems- one of size 4n/52 and another of size 42n/52 and so on.
→At the bottom most layer, the size of sub-problems will reduce to 1.
This is illustrated through following recursion tree.
 n 4n
T n =T +T +n
5 5
𝑛 𝑛 4𝑛 𝑛
𝑇 =𝑇 2 +𝑇 2 +
5 5 5 5
4𝑛 4𝑛 2
4 𝑛 4𝑛
𝑇 =𝑇 2 +𝑇 2 +
5 5 5 5
𝑛 𝑛 4𝑛 𝑛
𝑇 2 =𝑇 3 +𝑇 3 + 2
5 5 5 5

For level-2 we do this for each sub problem

T(n) Level-0
n Level-0

T(n/5) T(4n/5) Level-1

n/5 4n/5 Level-1

𝑛
𝑇( 2 ) Level-2 𝑛 4𝑛 4𝑛 42 𝑛 Level-2
5 4𝑛 4𝑛 4 𝑛 2
𝑇( 2 ) 𝑇( 2 ) 𝑇( 2 ) 52 52 52
5 5 5 52

K-Level
K-Level T(1) T(1) T(1) T(1)
T(1) T(1) T(1) T(1)
 Step-02:
 Determine cost of each level-
→ Cost of level-0 = 𝑛
𝑛 4𝑛
→ Cost of level-1 = + =𝑛
5 5
𝑛 4𝑛 4𝑛 42𝑛
→ Cost of level-2 = 2
+ 2
+ 2
+ =𝑛
5 5 5 52
 Step-03:
 Determine total number of levels in the recursion tree. We will consider the rightmost sub tree as it goes down to the deepest level:
4
→ Size of sub-problem at level-0 = ( )0 𝑛
5
4
→ Size of sub-problem at level-1 = ( )1 𝑛
5
4
→ Size of sub-problem at level-2 = ( )2 𝑛
5
 Continuing in similar manner, we have:
4
→ Size of sub-problem at level-I = ( )𝑖 𝑛
5
 Suppose at level-k (last level), size of sub-problem becomes 1. Then-
4 4 1
→( )𝑘 𝑛 = 1 ⇒ ( )𝑘 =
5 5 𝑛
 Multiplying both sides by 𝒍𝒐𝒈𝟒 , we get:
𝟓
1
→𝑘 = 𝒍𝒐𝒈𝟒 𝑛 ⇒ 𝑘 = 𝑙𝑜𝑔5 𝑛
𝟓 4
→Total number of levels in the recursion tree = 𝑙𝑜𝑔5 𝑛 + 1
4
Step-04:
Determine number of nodes in the last level-
→Level-0 has 20 nodes i.e., 1 node
→Level-1 has 21 nodes i.e., 2 nodes
→Level-2 has 22 nodes i.e., 4 nodes
Continuing in similar manner, we have:
𝑙𝑜𝑔5 𝑛
→Level- 𝑙𝑜𝑔5 𝑛 has 2 4 nodes.
4
Step-05:
Determine cost of last level-
𝑙𝑜𝑔5 𝑛 𝑙𝑜𝑔5 𝑛 𝑙𝑜𝑔 52
→Cost of last level =2 4 × T 1 = Θ(2 4 ) = Θ(𝑛 4 )
Step-06:
→Add costs of all the levels of the recursion tree and
simplify the expression so obtained in terms of
asymptotic notation:
𝒍𝒐𝒈 𝟓 𝟐
𝑻 𝒏 = 𝒏 + 𝒏 + 𝒏 + ⋯ + 𝜣(𝒏 𝟒 )
For 𝑙𝑜𝑔5 𝑛 levels
4
log5 2
= nlog 5 n + Θ(n 4 )
4
log5 2
= Θ(n 4 )
 Solve the following recurrence relation using recursion tree method

T(n) = 3T(n/4) + cn2 T n = 3T

n
4
+ c𝑛2
𝑛 𝑛 𝑛
Step-01:Draw a recursion tree based on the given recurrence relation: 𝑇
4
𝑛
= 3𝑇 2 + 𝑐( )2
4
𝑛
4
𝑛 2
𝑇 2 = 𝑇 3 + 𝑐( )
4 4 16

(Here, we have directly drawn a recursion tree representing the cost of sub problems)
Step-02:
Determine cost of each level-
→Cost of level-0 = 𝑐𝑛2
→Cost of level-1 = c(n/4)2 + c(n/4)2 + c(n/4)2 = (3/16)cn2
→Cost of level-2 = c(n/16)2 x 9 = (9/162)cn2
Step-03:
Determine total number of levels in the recursion tree:
→Size of sub-problem at level-0 = n/40
→Size of sub-problem at level-1 = n/41
→Size of sub-problem at level-2 = n/42
Continuing in similar manner, we have:
→Size of sub-problem at level-i = n/4i
Suppose at level-k (last level), size of sub-problem becomes 1. Then:
→n/4k = 1
→4k = n
Taking log on both sides, we get:
→𝑙𝑜𝑔44𝑘 = 𝑙𝑜𝑔4𝑛
→k = 𝑙𝑜𝑔4 𝑛
Total number of levels in the recursion tree = log𝟒𝒏 + 𝟏
Step-04:
Determine number of nodes in the last level-
→Level-0 has 30 nodes i.e., 1 node
→Level-1 has 31 nodes i.e., 3 nodes
→Level-2 has 32 nodes i.e., 9 nodes
Continuing in similar manner, we have-
→Level-log4n has 3𝑙𝑜𝑔4 𝑛 nodes i.e., 𝑛𝑙𝑜𝑔4 3 nodes
Step-05:
Determine cost of last level:
→Cost of last level = 𝑛𝑙𝑜𝑔4 3 × 𝑇 1 = Θ(𝑛𝑙𝑜𝑔4 3)
Step-06:
Add costs of all the levels of the recursion tree and simplify the expression so obtained in terms of
asymptotic notation:
= cn2 { 1 + (3/16) + (3/16)2 + ……… } + θ(nlog43)
Now, { 1 + (3/16) + (3/16)2 + ……… } forms an infinite Geometric progression.
On solving, we get:
2 3 4 5
2
3 2
3 2
3 2
3 2
3
= 𝑐𝑛 + 𝑐𝑛 + 𝑐𝑛 + 𝑐𝑛 + 𝑐𝑛 + 𝑐𝑛 2 + ⋯ + Θ(𝑛 𝑙𝑜𝑔4 3 )
16 16 16 16 16
2 3 4 5
3 3 3 3 3
= 𝑐𝑛 2 + + + + + ⋯ + Θ(𝑛 𝑙𝑜𝑔4 3 )
16 16 16 16 16

3
Geometric progression
𝑟= <1
16
To solve this applying geometric progression:
1 2 16
= 𝑐𝑛 2 3 = 𝑐𝑛
1− 13
16

𝑻𝒉𝒖𝒔, 𝑻 𝒏 = 𝜣(𝒏𝟐 )
Geometric progression
Master Method (Method 1)
 Complexity of Recursive Algorithms – Master
Theorem
This recurrence describes an algorithm that divides a problem of size 𝑛 into a subproblems,
each of size 𝑛/𝑏, and solves them recursively.
The master method gives us a quick way to find solutions to recurrence relations of the form:
𝒏
𝑻 𝒏 = 𝒂𝑻 + 𝒇(𝒏) with 𝒂 ≥ 𝟏 and 𝒃 > 𝟏.
𝒃
→𝒂 represents how many recursive calls are made, (Binary search has 1 split, while Merge
sort has 2 split, etc.)
→𝒃 represents the factor by which the work is reduced in each recursive call, (for example,
Binary search and merge sort cut input in half).
→𝒇(𝒏) reparents how much work is done by each call apart from the recursion, as a function
of 𝑛. for example 𝑂(𝑛), 𝑂(1).
Once we have 𝑎, 𝑏, 𝑎𝑛𝑑 𝑓(𝑛) we can determine the runtime of the work done by the recursion.
Finally, we compare the runtime of the split recursion functions and 𝑓(𝑛).
Theorem
 Quick Description
A utility method for analyzing recurrence relations.
Useful in many cases for divide and conquer algorithms
There recurrence relations are of the form:
𝒏
𝑻 𝒏 = 𝒂𝑻 𝒃
+ 𝒇(𝒏) with 𝒂 ≥ 𝟏 and 𝒃 > 𝟏.

→𝑛 = the size of the current problem.

→𝑎 = the number of subproblems in the recursion.
→𝑛/𝑏 = the size of each subproblem.
→𝑓(𝑛) = the cost of the work that must be done outside the recursive
calls(cost of dividing + merging)
 The three cases of the Master Method
 Case-1: The running time is dominated by the cost at the leaves:
if f n = 𝑂 𝑛𝑙𝑜𝑔𝑏 𝑎 −𝜀 , 𝑡ℎ𝑒𝑛 𝑇 𝑛 = 𝜃 𝑛𝑙𝑜𝑔𝑏 𝑎 for ε > 0

Case-2: The running time is distributed throughout by the tree:

if f n = Θ 𝑛𝑙𝑜𝑔𝑏 𝑎 , 𝑡ℎ𝑒𝑛 𝑇 𝑛 = 𝜃 𝑛𝑙𝑜𝑔𝑏 𝑎 log(𝑛)

Case-3: The running time is dominated by the cost at the root:

if f n = Ω 𝑛𝑙𝑜𝑔𝑏 𝑎 +𝜀 , 𝑡ℎ𝑒𝑛 𝑇 𝑛 = 𝜃 𝑓(𝑛) for ε > 0
→For case-3: f(n) should satisfy the regularity condition:
𝑛
𝑎𝑓 ≤ 𝑐𝑓 𝑛 𝑤ℎ𝑒𝑟𝑒 𝑐 < 1 (This is always holds for polynomials)
𝑏
Because of this condition, the Master Method cannot solve every recurrence of
the given form.
 How to apply the Master Method
𝒏
𝑻 𝒏 = 𝒂𝑻 + 𝒇(𝒏)
a
𝒃
F(n)
b

Extract a, b and f(n) from the given recurrence.

Determine 𝑛𝑙𝑜𝑔𝑏 𝑎 .
Compare 𝑓(𝑛) and 𝑛𝑙𝑜𝑔𝑏 𝑎 asymptomatically.
Determine the appropriate Master Method case and apply it.
 𝒏
Example 1: 𝑻 𝒏 = 𝟐𝑻 +𝒏
𝟐
 Solution:
→Extract: 𝑎 = 2, 𝑏 = 2, 𝑎𝑛𝑑 𝑓 𝑛 = 𝑛
→Determine: 𝑛𝑙𝑜𝑔𝑏 𝑎 = 𝑛𝑙𝑜𝑔2 2 = 𝑛1 = 𝑛.
→Compare: 𝑓 𝑛 𝑎𝑛𝑑 𝑛𝑙𝑜𝑔𝑏 𝑎
𝑓 𝑛 = 𝑛𝑙𝑜𝑔𝑏 𝑎 = 𝑛

→Because 𝑓 𝑛 = 𝑛𝑙𝑜𝑔𝑏 𝑎
= 𝑛; thus, we apply Case-2 (evenly distributed.
• 𝑓 𝑛 =Θ 𝑛 ,
• 𝑇 𝑛 = Θ 𝑛 𝑙𝑜𝑔𝑏 𝑎 log 𝑛
= Θ 𝑛1 log 𝑛
= Θ 𝑛 log 𝑛
 𝒏
Example 2: 𝑻 𝒏 = 𝟗𝑻 +𝒏
𝟑
Solution:
→Extract: 𝑎 = 9, 𝑏 = 3, 𝑎𝑛𝑑 𝑓 𝑛 = 𝑛
→Determine: 𝑛𝑙𝑜𝑔𝑏 𝑎 = 𝑛𝑙𝑜𝑔3 9 = 𝑛2.
→Compare: 𝑓 𝑛 𝑎𝑛𝑑 𝑛𝑙𝑜𝑔𝑏 𝑎
𝑓 𝑛 =𝑛
(𝑎)
𝑙𝑜𝑔𝑏
𝑛 = 𝑛2
(𝑎)
𝑙𝑜𝑔𝑏
𝑓 𝑛 <𝑛
→Because 𝑓 𝑛 < 𝑛𝑙𝑜𝑔𝑏 𝑎 ; thus, we apply Case-1:
• 𝑓 𝑛 = 𝑂 𝑛𝑙𝑜𝑔𝑏 𝑎 −𝜀
= 𝑂 𝑛2−𝜖
• 𝑇 𝑛 = 𝜃 𝑛𝑙𝑜𝑔𝑏 𝑎
= Θ 𝑛2 .
 𝒏
Example 3: 𝑻 𝒏 = 𝟑𝑻 + 𝒏𝒍𝒐𝒈(𝒏)
𝟒
Solution:
→Extract: 𝑎 = 3, 𝑏 = 4, 𝑎𝑛𝑑 𝑓 𝑛 = 𝑛𝑙𝑜𝑔𝑛
→Determine: 𝑛 𝑙𝑜𝑔𝑏 𝑎 = 𝑛 𝑙𝑜𝑔4 3 . In this case 𝑙𝑜𝑔4 3 < 1. ≈0.79248125
→Compare: 𝑓 𝑛 𝑎𝑛𝑑 𝑛 𝑙𝑜𝑔𝑏 𝑎 .
𝑓 𝑛 = 𝑛𝑙𝑜𝑔𝑛
(𝑎)
𝑙𝑜𝑔𝑏
𝑛 = 𝑙𝑜𝑔4 3
𝑓(𝑛) > 𝑛 𝑙𝑜𝑔𝑏 𝑎
→Because 𝑓 𝑛 > 𝑛 𝑙𝑜𝑔𝑏 𝑎 ; thus, we apply Case-3; however, we must check the regularity
condition.
𝑛
• This should be true: 𝑎𝑓 ≤ 𝑐𝑓 𝑛 𝑤ℎ𝑒𝑟𝑒 𝑐 < 1
𝑏
𝑛 𝑛
• 𝑎 𝑙𝑜𝑔 ≤ 𝑐 𝑛𝑙𝑜𝑔𝑛
𝑏 𝑏
3 𝑛 3
• 𝑛𝑙𝑜𝑔 ≤ 𝑐𝑛𝑙𝑜𝑔𝑛; this is true for example if 𝑐 = .
4 4 𝑎 +𝜀 4
𝑙𝑜𝑔𝑏
• 𝑓 𝑛 =Ω 𝑛 = Ω 𝑛 𝑙𝑜𝑔4 3 +𝜀

• 𝑇 𝑛 = 𝜃 𝑓(𝑛)
= Θ 𝑛𝑙𝑜𝑔𝑛 .
Example 4: What the runtime of this recursion?
Case1(n){
 Let us identify a, b and f(n) from the master theorem. If(!n){
 Sub problems? 2, so 𝑎 = 2 Return 1;
1
}
 Sub problems is of the original n size, thus 𝑏 = 4. Return case1(n/4)+case1(n/4)
4
 Runtime without recursion is constant, 𝑓(𝑛) = 1
𝑛
 Substituting the values into the formula 𝑇 𝑛 = 𝑎. 𝑇 + 𝑓 𝑛 we get:
𝑏
𝑛
𝑇 𝑛 = 2. 𝑇 +1
4
What is the runtime of the recursion by itself? Using the formula 𝑛𝑙𝑜𝑔𝑏 𝑎 we get:
𝑛𝑙𝑜𝑔𝑏 𝑎 = √𝑛
Comparing 𝑓(𝑛) with the result in the previous step, we see it matches case 1.
Since 𝑂 𝑛 > 𝑂 1 then the runtime is 𝑛𝑙𝑜𝑔𝑏 𝑎
1
• 𝑓 𝑛 = 𝑂 𝑛𝑙𝑜𝑔𝑏 𝑎 −𝜀 = 𝑂 𝑛2−𝜖
• 𝑇 𝑛 = 𝜃 𝑛𝑙𝑜𝑔𝑏 𝑎

• Θ( 𝑛)
MASTER Theorem (Method 2)
 Master Theorem for Dividing Functions
The general for of recurrence relation is:
𝑛
𝑇 𝑛 = 𝑎𝑇 + 𝑓(𝑛)
𝑏
We assume that:
𝑎 ≥ 1, 𝑏 > 1, 𝑓 𝑛 = Θ 𝑛𝑘 𝑙𝑜𝑔𝑝 𝑛
From this relation we need to find:
a) 𝑙𝑜𝑔𝑏 𝑎
b) 𝑘
Based on these two values we have 3 cases as follows:
 Master Theorem for Dividing Functions
Case 1: if 𝑙𝑜𝑔𝑏 𝑎 > 𝑘 then Θ 𝑛𝑙𝑜𝑔𝑏𝑎 .
Case 2: if 𝑙𝑜𝑔𝑏 𝑎 = 𝑘, then we will have 3 sub-cases:
a) If 𝑝 > −1, 𝑡ℎ𝑒𝑛 Θ 𝑛 𝑘 𝑙𝑜𝑔𝑝+1 𝑛 .
b) If 𝑝 = −1, 𝑡ℎ𝑒𝑛 Θ 𝑛 𝑘 𝑙𝑜𝑔𝑙𝑜𝑔𝑛 .
c) If 𝑝 < −1, 𝑡ℎ𝑒𝑛 Θ 𝑛 𝑘
Case 3: if 𝑙𝑜𝑔𝑏 𝑎 < 𝑘, then we will have 2 sub-cases:
a) If 𝑝 ≥ 0, 𝑡ℎ𝑒𝑛 Θ 𝑛 𝑘 𝑙𝑜𝑔𝑝 𝑛 .
b) If 𝑝 < 0, 𝑡ℎ𝑒𝑛 Θ 𝑛𝑘 .
 𝑛
Example: 𝑇 𝑛 = 2𝑇 2
+1
Solution:
→𝑎 = 2
→𝑏 = 2
→𝑓 𝑛 = Θ 1 = Θ 𝑛0𝑙𝑜𝑔0 𝑛
→𝐾 = 0
→𝑃 = 0
𝑙𝑜𝑔𝑏 𝑎 = 𝑙𝑜𝑔2 2 = 1
→𝑙𝑜𝑔𝑏 𝑎 > 𝑘
→Then case 1 is the solution: Θ 𝑛𝑙𝑜𝑔𝑏 𝑎 = Θ(𝑛1 ) = Θ 𝑛 .
Exercise: Use the Master Method to solve
1. 𝑇(𝑛) = 4𝑇(𝑛/2) + 𝑛
2. 𝑇(𝑛) = 8𝑇(𝑛/2) + 𝑛
3. 𝑇(𝑛) = 8𝑇(𝑛/2) + 𝑛𝑙𝑜𝑔𝑛
4. 𝑇(𝑛) = 2𝑇(𝑛/2) + 𝑛
5. 𝑇(𝑛) = 4𝑇(𝑛/2) + 𝑛2
6. 𝑇(𝑛) = 4𝑇(𝑛/2) + 𝑛2 𝑙𝑜𝑔2 𝑛
 References
Required References
1. Sandeep Sen (Author), Amit Kumar (Author) , Design and Analysis of Algorithms: A
Contemporary Perspective, Cambridge University Press (May 23, 2019).

Further Readings
1. Divyansh Pratap Singh Parmar, Data structure and Algorithm: COMPUTER SCIENCE,
Independently published, 2019.
2. Michael Soltys-Kulinicz , Introduction To The Analysis Of Algorithms, World Scientific
Publishing Co Pte Ltd , 3rd edition (March 30, 2018).
3. Rosen, K. H. Discrete Mathematics and Its Applications.
4. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to algorithms.
MIT press.
 Thank you
Any questions?
42