Recursion

P R E PA RED BY
L. MA RY S HA MAL A
A S S ISTANT P ROF ESSOR/SCOP E
Recursion
▪A recursive function is defined as a function that calls itself to solve
a smaller version of its task until a final call is made which does not
require a call to itself.
▪Since a recursive function repeatedly calls itself, it makes use of the
system stack to temporarily store the return address and local
variables of the calling function.

VIT/SCOPE/DSA-BCSE202L/M1 4
Recursive Algorithm
▪To solve a problem, solve a subproblem that is a smaller instance of
the same problem, and then use the solution to that smaller
instance to solve the original problem.
▪Every recursive solution has two major cases.
1. Recursive Case : Each recursive call should be on a smaller instance
of the same problem, that is, a smaller subproblem.
2. Base case-Problem is simple enough to be solved directly.

VIT/SCOPE/DSA-BCSE202L/M1 5
Example 1:Factorial of a Number
▪Product of all consecutive Integer numbers up to n is called Factorial
of a number and is denoted by n!
▪To calculate n!, we multiply the number with factorial of the number
that is 1 less than that number.
n! = n × (n–1)!

VIT/SCOPE/DSA-BCSE202L/M1 6
Example 1…
▪The recursive solution for the factorial function
◦ Base case is when n = 1, because if n = 1, the result will be 1 as 1! = 1.
◦ Recursive case of the factorial function will call itself but with a smaller value
of n, this case can be given as factorial(n) = n × factorial (n–1)
▪We can define the Factorial function as:
Fact(n) = 1 for n = 1
Fact(n) = n*Fact(n-1) for n > 1

VIT/SCOPE/DSA-BCSE202L/M1 7
Recursive Algorithm for Factorial
Algorithm Factorial(n)
// Input: An integer number n
// Output: Factorial of n
Read n
fact  1
if n==1 then
return 1
else
fact  n*Factorial(n-1)
return fact

VIT/SCOPE/DSA-BCSE202L/M1 8
Types of Recursion
Any recursive function can be characterized based on:
◦ whether the function calls itself directly or indirectly (direct or indirect
recursion)
◦ whether any operation is pending at each recursive call (tail recursive or not),
◦ the structure of the calling pattern (linear or tree-recursive).

VIT/SCOPE/DSA-BCSE202L/M1 9
Advantages of Recursion
▪Recursive solutions often tend to be shorter and simpler than non-
recursive ones.
▪Code is clearer and easier to use.
▪Recursion works similar to the original formula to solve a problem.
▪Recursion follows a divide and conquer technique to solve
problems.
▪In some (limited) instances, recursion may be more efficient

VIT/SCOPE/DSA-BCSE202L/M1 10
Disadvantages of Recursion
▪For some programmers and readers, recursion is a difficult concept.
▪Recursion is implemented using system stack. If the stack space on
the system is limited, recursion to a deeper level will be difficult to
implement.
▪Aborting a recursive program in midstream can be a very slow
process.
▪Using a recursive function takes more memory and time to execute
as compared to its non-recursive counterpart.
▪It is difficult to find bugs, particularly while using global variables.

VIT/SCOPE/DSA-BCSE202L/M1 11
Recursion versus Iteration
▪Recursion is more of a top-down approach. On the contrary,
iteration follows a bottom-up approach
▪Recursion is an excellent way of solving complex problems.
▪However, recursive solutions are not always the best solutions. In
some cases, recursive programs may require substantial amount of
run-time and memory space.
▪One must use recursion only to find solution to a problem for which
no obvious iterative solution is known.

VIT/SCOPE/DSA-BCSE202L/M1 12
Example 2: Fibonacci series
A series of numbers in which each number is the sum of the two
preceding or previous numbers is called Fibonacci Series.
For example, Fibonacci series upto 7 numbers is 0,1, 1, 2, 3, 5, 8.
i.e. To get nth position number, you should add (n-2) and (n-1)
position number.
Write pseudocode to generate Fibonacci series

VIT/SCOPE/DSA-BCSE202L/M1 13
Iterative Algorithm for Fibonacci series
Algorithm Fibonacci(n)
//Input: A non-negative integer number n
//Output: A series of ‘n’ numbers in which each number is the sum of the two preceding numbers
read n
f0  0
f1  1
i2
write f0, f1
do
fib=f0+f1
write fib
f0  f1
f1  fib
i i+1
while (i < n)
The overall time complexity of the Fibonacci function: T(n)=O(n)
VIT/SCOPE/DSA-BCSE202L/M1 14
Iterative Algorithm for nth number in
Fibonacci Sequence
Firstly, the assignments of A[0]
and A[1] cost O(1) each.
Secondly, loop performs one
assignment per iteration and executes
(n-1)-2 times, costing a total of O(n-3)
= O(n).
Therefore, our iterative algorithm
has a time complexity of
O(n) + O(1) + O(1) = O(n)

VIT/SCOPE/DSA-BCSE202L/M1 15
Recursive Algorithm
➢The Fibonacci Sequence is an infinite sequence of positive integers, starting
at 0 and 1, where each succeeding element is equal to the sum of its two
preceding elements.
➢If we denote the number at position n as Fn, we can formally define the
Fibonacci Sequence as:
Fn = 0 for n = 0
Fn = 1 for n = 1
Fn = Fn-1 + Fn-2 for n > 1
➢Therefore, the sequence is:
0, 1, 1, 2, 3, 5, 8, 13, …

VIT/SCOPE/DSA-BCSE202L/M1 18
➢To evaluate F(n) for n > 1, we can reduce our problem into
two smaller problems of the same kind: F(n-1) and F(n-2).

➢The Algorithm for F(n) will have two steps:

1. Check if n ≤ 1. If so, return n.
2. Check if n > 1. If so, call our function F with inputs n-1
and n-2, and return the sum of the two results.

VIT/SCOPE/DSA-BCSE202L/M1 19
Analysis of Time Complexity
➢We can analyze the time complexity of F(n) by counting the number of times
its most expensive operation will execute for n number of inputs.
For this algorithm, the operation contributing the greatest runtime cost is
addition.
➢Finding an Equation for Time Complexity
• Let T(n) denote the time complexity of F(n).
• The number of additions required to compute F(n-1) and F(n-2) will then be T(n-1) and T(n-2),
respectively. We have one more addition to sum our results.
• Therefore, for n > 1: T(n) = T(n-1) + T(n-2) + 1 ------------------------(1)
• When n = 0 and n = 1, no additions occur. This implies that: T(0) = T(1) = 1

VIT/SCOPE/DSA-BCSE202L/M1 20
Analysis of Time Complexity
Simplifying T(n)
•Assume that T(n-2) ≈ T(n-1). [Since T(n-2) ≤ T(n-1) will always hold]
•Substituting the value of T(n-2) = T(n-1) into our relation T(n) ie, in equation (1),
we get:
T(n) = T(n-1) + T(n-1) + 1 = 2*T(n-1) + 1 -----------(2)
•By doing this, we have reduced T(n) into a much simpler recurrence.
•As a result, we can now solve for T(n) using backward substitution.
•The result will give us an upper bound on the time complexity of T(n).

VIT/SCOPE/DSA-BCSE202L/M1 21
Analysis of Time Complexity…
Solving T(n) Using Backward Substitution
1. First substitute T(n-1) into the right-hand side of our recurrence ie, equation (2).
Since T(n-1) = 2*T(n-2) + 1, we get:
T(n) = 2*[2*T(n-2) + 1] + 1 = 4*T(n-2) + 3
2. Next, we can substitute in T(n-2) = 2*T(n-3) + 1:
T(n) = 2*[2*[2*T(n-3) + 1] + 1] + 1 = 8*T(n-3) + 7
3. And once more for T(n-3) = 2*T(n-4) + 1:
T(n) = 2*[2*[2*[2*T(n-4) + 1]+ 1] + 1] + 1 = 16*T(n-4) + 15
➢The general solution for T(n):
T(n) = 2k*T(n–k) + (2k-1), for any positive k

VIT/SCOPE/DSA-BCSE202L/M1 22
Analysis of Time Complexity…
➢Solving T(n), by substituting T(0) = 1 and k values.
➢For T(0), n – k = 0. Rearranging, we get k = n.
➢Now, substituting in our values for T(0) and k, we get:
T(n) = 2n*T(0) + (2n-1)
= 2n + 2n – 1
= O(2n)
Thus the run time of our algorithm will grow exponentially in n.

VIT/SCOPE/DSA-BCSE202L/M1 23
Towers of Hanoi

VIT/SCOPE/DSA-BCSE202L/M1 24
Problem
▪The problem is to move all these rings from pole A to pole C
while maintaining the same order.
▪A few rules to be followed for Tower of Hanoi are
◦ Only one disk can be moved among the towers at any given time.
◦ Only the "top" disk can be removed.
◦ No large disk can sit over a small disk.

VIT/SCOPE/DSA-BCSE202L/M1 25
Recursive Solution
The solution to our problem of moving n rings from A to C
using B as spare can be given as:
◦ Base case: if n=1 , Move the ring from A to C using B as spare
◦ Recursive case:
◦ Move n – 1 rings from A to B using C as spare
◦ Move the one ring left on A to C
◦ Move n – 1 rings from B to C using A as spare
It says, ‘if you can solve n–1 cases, then you can easily solve
the nth case’.

VIT/SCOPE/DSA-BCSE202L/M1 26
Working of Tower of Hanoi with Three Disks

VIT/SCOPE/DSA-BCSE202L/M1 29
Recursive algorithm for Tower of Hanoi
Algorithm ToH(n,A,B,C)
{
if (n ≥ 1) then
ToH(n-1, A,B,C);
write(”Move to disk from tower” ,A, ”to top of tower”, B);
ToH(n-1,C,B,A);
else
write(”Move to disk from tower” ,A, ”to top of tower”, C)
}
VIT/SCOPE/DSA-BCSE202L/M1 31
Complexity Analysis of Tower Of Hanoi
Moving n-1 disks from source to aux means the first peg to the second
peg (in our case). This can be done in T (n-1) steps.
Moving the nth disk from source to destination means a larger disk from
the first peg to the third peg will require 1 step.
Moving n-1 disks from aux to destination means the second peg to the
third peg (in our example) will require again T (n-1) step.
So, total time taken T (n) = T (n-1)+ 1 + T(n-1)
The recurrence relation is T(n) = 2T(n-1) + 1 ———— (1) for n>1
◦ =1 for n=1

VIT/SCOPE/DSA-BCSE202L/M1 32
Try by Yourself
Recursively solve the puzzle of shifting disks 1 , 2 , 3 from Rod A to
Rod B.

VIT/SCOPE/DSA-BCSE202L/M1 33
Recurrences

VIT/SCOPE/DSA-BCSE202L/M1 34
Divide and Conquer
▪Divide the problem into a number of subproblems that are smaller instances of
the same problem.
▪Conquer the subproblems by solving them recursively. If the subproblem sizes
are small enough, however, just solve the subproblems in a straightforward
manner.
▪Combine the solutions to the subproblems into the solution for the original
problem.
▪When the subproblems are large enough to solve recursively, we call that the
recursive Case
▪Once the subproblems become small enough that we no longer recurse, the
base case.

VIT/SCOPE/DSA-BCSE202L/M1 35
Recurrences
▪Recurrences go hand in hand with the divide-and-conquer paradigm
▪A recurrence is an equation or inequality that describes a function in terms of
its value on smaller inputs
▪Recurrences can take many forms
▪For example, a recursive algorithm might divide subproblems into unequal sizes,
such as a 2/3 to 1/3 split. If the divide and combine steps take linear time, such
an algorithm would give rise to the recurrence
T(n)=T(2n/3)+T(n/3)+1
▪Subproblems are not necessarily constrained to being a constant fraction of the
original problem size. Each recursive call would take constant time plus the time
for the recursive calls it makes, yielding the recurrence
T(n)=T(n-1)+1

VIT/SCOPE/DSA-BCSE202L/M1 36
Recurrence Relation
Definition : A Recurrence Relation for a sequence {an} is an equation that
express an in terms of one or more of the previous terms in the sequence,
a0, a1, a2, a3, ... an for all integers n≤ n0 where n0 is a non-negative integer.
▪A sequence is called a solution of a recurrence relation if its terms satisfy
the recurrence relation.
▪Motivating Examples:
▪ Finding the Factorial of a given number, Fibonacci series, Towers of Hanoi, etc.
▪ Some of the problems solved by DAC approach: Maximum Subarray Problem,
Strassen’s Algorithm for Matrix multiplication

VIT/SCOPE/DSA-BCSE202L/M1 37
Simple Example
▪Assume we have a set of integers as like 1,2,4,8,16,32,..
▪What will be the next integer in above set?
▪64
After giving the first term, each term of the sequence can be defined
from the previous term.
a1= 1 =>an-1 = 2an
When a sequence is defined recursively, mathematical induction can
be used to prove results about the sequence.

VIT/SCOPE/DSA-BCSE202L/M1 38
Recurrence Relation…
A recurrence relation is like a recursively defined sequence, but
without specifying any initial values (initial conditions).
Therefore, the same recurrence relation can have multiple solutions.
If both the initial conditions and the recurrence relation are
specified, then the sequence is uniquely determined
More generally, recurrences are of form
T(n) = 𝛼𝑇 𝑛 − 𝛽 + 𝑓 𝑛 , 𝑇 𝛿 = 𝑐 or
T(n) = 𝛼𝑇 𝑛/𝛽 + 𝑓 𝑛 , 𝑇 𝛿 = 𝑐 is the initial condition

39
Practice
Find the recurrence relation for binary search
Solution : Recurrence relation for binary search is
1 𝑖𝑓 𝑛 = 1
𝑇 𝑛 =ቊ 𝑛
𝑇( Τ2) + 1, 𝑖𝑓 𝑛 > 1

VIT/SCOPE/DSA-BCSE202L/M1 40
Practice …
1. Maximum subarray Problem:it takes as input an array of numbers,
and it determines the contiguous subarray whose values have the
greatest sum
1 𝑖𝑓 𝑛 = 1
𝑇 𝑛 =ቊ
2𝑇(𝑛Τ2) + 𝑛, 𝑖𝑓 𝑛 > 1

2. Strassen’s Matrix Multiplication

1 𝑖𝑓 𝑛 = 1
𝑇 𝑛 =ቊ
7𝑇(𝑛Τ2) + 𝑛2 , 𝑖𝑓 𝑛 > 1
VIT/SCOPE/DSA-BCSE202L/M1 41
Solving Recurrence Relations
1. Iteration Method
2. Substitution Method
3. Master Theorem Method
4. Recurrence Tree Method

VIT/SCOPE/DSA-BCSE202L/M1 42
Method of Iteration
Let {ai} be the sequence defined by: ak = ak−1 + 2 with a0 = 1.
Plugging values of k into the relation, we get:
a1 = a 0 + 2 = 1 + 2
a2 = a1 + 2 = 1 + 2 + 2 = 1 + 2(2)
a3 = a2 + 2 = 1 + 2 + 2 + 2 = 1 + 3(2)
a4 = a3 + 2 = 1 + 2 + 2 + 2 + 2 = 1 + 4(2)
Continuing in this fashion reinforces the apparent pattern that
an = 1 + n(2) = 1 + 2n
This brute force technique is the Method of Iteration.
VIT/SCOPE/DSA-BCSE202L/M1 43
Estimating upper and lower bounds
▪"Making a good guess" method.
▪ Guess the form of the answer
▪ Use Induction to find the constants and show that solution works.
▪This method can be used to establish either upper or lower bounds
on a recurrence.
▪This method can be applied only when it is easy to guess the form of
the answer.

VIT/SCOPE/DSA-BCSE202L/M1 44
Example 1
Use the guessing technique to find the asymptotic bounds for
Mergesort, whose running time is described by the equation
T(n)=2T(n/2)+n; T(2)=1.
We begin by guessing that this recurrence has an upper bound
in O(n2).
Ie, assume that T(n)≤ n2
Proof by induction
For the base case, T(2)=1≤22

VIT/SCOPE/DSA-BCSE202L/M1 45
Example 1…
For the induction step,
we need to show that T(n)≤ n2 implies that T(2n)≤(2n)2 for n=2N,N≥1
Assume the Induction hypotheses as T(i)≤i2, for all i≤n.
It follows that
T(2n)=2T(n)+2n≤2n2+2n≤4n2≤(2n)2
which is what we wanted to prove.
Thus, T(n) is in O(n2).

VIT/SCOPE/DSA-BCSE202L/M1 46
Example 2
T(n) = 2T(n/2) + n
The guess solution is T(n) = O(n log n).
Assume (induction hypothesis) as T(n)≤nlogn. Then,
T(n) ≤ 2(n/2)log (n/2) + n
≤ cnlog (n/2) + n
= cnlogn - cnlog2 + n
= cnlogn - cn + n
<cnlogn; c> 1:

VIT/SCOPE/DSA-BCSE202L/M1 48
Disadvantage of Estimation Method
There is no general way to guess the correct solution to the
recursion.
Guessing a solution takes experience and, occasionally, creativity.
Some heuristics that can help you become a good guesser
We can use recursion trees to generate good guess to recursion.
Estimating bounds is effective if you only need an approximation to
the answer.
More precise techniques are required to find an exact solution.

VIT/SCOPE/DSA-BCSE202L/M1 50
Substitution Method
Expanding recurrences
The smaller terms on the right side of the equation are in turn
replaced by their definition. This is the expanding step.
These terms are again expanded, and so on, until a full series with no
recurrence results.
This yields a summation, and techniques for solving summations can
then be used.

VIT/SCOPE/DSA-BCSE202L/M1 51
Example 1
T(n)=2T(n-1)
=2[2T(n-2)]= 22. T(n-2)
= 22[2T(n-3)]= 23. T(n-3)
= 23[2T(n-4)]= 24. T(n-4)
…. Repeat the procedure for k times
T(n)=2k. T(n-k) ----------------(1)
Put n-k=1=> k=n-1
Substitute in (1)➔ T(n)= 2n-1 T(1)
= 2n-1 .1
= 2n-1 [Max of 2n and ½]
Therefore, T(n)=O(2n)

VIT/SCOPE/DSA-BCSE202L/M1 52
Example 2
T(n)= 2T(n/2)+n, n>1; T(1)=1
Solution
T(n)= 2T(n/2)+n -------------(1)
=2[2T(n/22)+n/2]+n = 22T(n/22)+2n -------------(2)
=22 [2T(n/23)+n/ 22 ]+2n =23T(n/23)+3n -------------(3)
=23 [2T(n/24)+n/ 23]+3n =24T(n/24)+4n ---------------(4)
…. Repeat the procedure for k times
T(n)=2k. T(n/2k)+kn -------------(5)

VIT/SCOPE/DSA-BCSE202L/M1 53
Example 2…
When n=1, T(1)=1
Therefore, Assume n/2k=1=> 2k=n =>k=log2n
Substitute in equation(5)➔ T(n)= 2logn T(1)+n .logn
= n.1+nlogn
Therefore, T(n)=O(nlogn)

VIT/SCOPE/DSA-BCSE202L/M1 54
Change of variables (Substitution
Method)
T(n) = 2T( 𝑛 ) + log n.
Let m = log n, i.e. n = 2m.
Then T(2m) = 2T(2m/2 ) + m.
Now let S(m) = T(2m).
Then S(m) = 2S(m/2) + m.
This recurrence has the solution S(m) = O(m log m).
So T(n) = T(2m) = S(m) = O(m log m) = O(log n log log n).

VIT/SCOPE/DSA-BCSE202L/M1 55
Exercises
1. T(n)= 4T(n/2)+n
2. T(n)=4T(n/2)+n2
3. T(n)=4T(n/2)+n3
4. T(n)=4T(n/2)+n2logn

VIT/SCOPE/DSA-BCSE202L/M1 56
Recurrence Tree Method
A recursion tree is a tree where each node represents the cost of a
certain recursive subproblem. Then you can sum up the numbers in
each node to get the cost of the entire algorithm.
The recurrence tree method is most useful when the recurrence
relation splits the given problem into subproblems of uniform size.
The recursion tree method is good for generating guesses for the
substitution method.
Steps:
1. Expanding the recurrence into a tree
2. Summing the cost at each level
VIT/SCOPE/DSA-BCSE202L/M1 57
Example1: T(n) = 2T(n/2) + n

VIT/SCOPE/DSA-BCSE202L/M1 58
Example1…
First, determine the number of levels in the recursion tree.
Since each level of the tree splits each of the nodes in that level to
half the size of their parents, one can conclude that the total number
of levels here is log2n.
At each level, the sum of the nodes is n. Therefore, the overall time
complexity is given by:
T(n) = n + n + .... log2n times
= n ( 1 + 1 + ....log2n times)
= n log2n
= O(n log2n)

VIT/SCOPE/DSA-BCSE202L/M1 59
Example 2
T(n)=2T(n/2)+n2
Solution: The Recursion tree for the above recurrence is

VIT/SCOPE/DSA-BCSE202L/M1 60
Example 2…

VIT/SCOPE/DSA-BCSE202L/M1 61
Example 2…
Summing up the costs
T(n)=n2+n2/2+n2/4+…+log n times
≤n2(1+1/2+1/4+….)
𝑙𝑜𝑔𝑛 1
≤n σ𝑖=1 𝑖
2
2
1
≤ n2 1
1−
2
≤2n2
Time complexity =O(n2)

VIT/SCOPE/DSA-BCSE202L/M1 62
Example 3
Solve T(n) = T(n/4) + T(n/2) + n2

(a) Step 1 (b)Step 2

VIT/SCOPE/DSA-BCSE202L/M1 72
Example 3…

VIT/SCOPE/DSA-BCSE202L/M1 73
Example 3…

VIT/SCOPE/DSA-BCSE202L/M1 74
Example 3…

VIT/SCOPE/DSA-BCSE202L/M1 75
Example 3…

VIT/SCOPE/DSA-BCSE202L/M1 76
Example 3…

VIT/SCOPE/DSA-BCSE202L/M1 77
Practice
𝑇 𝑛 = 2𝑇(𝑛/2) + 𝑛
𝑇 𝑛 = 8𝑇(𝑛/2) + 𝑛2
𝑇 𝑛 = 3𝑇(𝑛/4) + 𝑐𝑛2

VIT/SCOPE/DSA-BCSE202L/M1 78
The Master Method
The master method provides a “cookbook” method for solving divide and
conquer recurrences of the form
𝑛
𝑇 𝑛 = 𝑎𝑇 +𝑓 𝑛
𝑏
where a≥ 1 and b > 1 are constants and f(n) is asymptotically positive.

This theorem can be applied wherever appropriate, rather than re-

deriving the solution for recurrence
This approach takes advantage of known theorems that provide the
solution for classes of recurrences

VIT/SCOPE/DSA-BCSE202L/M1 79
The Master Theorem
Let a≥ 1 and b > 1 be constants, f(n) be a function and let T(n) be defined
on non-negative integers by the recurrence:
𝑛
𝑇 𝑛 = 𝑎𝑇 +𝑓 𝑛
𝑏
Then T(n) has the following asymptotic bounds:
1. 𝐼𝑓 𝑓 𝑛 = Ο 𝑛log𝑏 𝑎−𝜀 𝑓𝑜𝑟 𝑠𝑜𝑚𝑒 𝑐𝑜𝑛𝑠𝑡𝑎𝑛𝑡 𝜀 > 0, 𝑡ℎ𝑒𝑛 𝑇 𝑛 =
Θ 𝑛log𝑏 𝑎
2. 𝐼𝑓 𝑓 𝑛 = Θ 𝑛log𝑏 𝑎 , 𝑡ℎ𝑒𝑛 𝑇 𝑛 = Θ 𝑛log𝑏 𝑎 log 𝑛
3. 𝐼𝑓 𝑓 𝑛 = Ω 𝑛log𝑏 𝑎+𝜀 𝑓𝑜𝑟 𝑠𝑜𝑚𝑒 𝑐𝑜𝑛𝑠𝑡𝑎𝑛𝑡 𝜀 > 0, 𝑎𝑛𝑑 𝑖𝑓 𝑎𝑓(𝑛/
𝑏) ≤ 𝑐𝑓(𝑛) 𝑡ℎ𝑒𝑛 𝑇 𝑛 = Θ 𝑓(𝑛)

VIT/SCOPE/DSA-BCSE202L/M1 80
The Master Theorem…
The master theorem compares the function f(n) with the function 𝑛log𝑏 𝑎 .
Case 1: f(n) is O(𝒏𝒍𝒐𝒈𝒃 𝒂 − ε) for some constant ε>0. Since the leaves grow faster
than f, asymptotically all of the work is done at the leaves, so T(n) is Θ(𝑛log𝑏 𝑎 ).
Case 2: f(n) is Θ(𝒏𝒍𝒐𝒈𝒃 𝒂 ). The leaves grow at the same rate as f, so the same
order of work is done at every level of the tree. The tree has O(log n) levels,
times the work done on one level, yielding T(n) is Θ(𝑛log𝑏 𝑎 log n).
Case 3: f(n) is Ω(𝒏𝒍𝒐𝒈𝒃 𝒂 + ε) for some constant ε>0. In this case f grows faster
than the number of leaves, which means that asymptotically the total amount of
work is dominated by the work done at the root node. For the upper bound, we
also need an extra smoothness condition on f in this case, namely that af(n/b)
≤ cf(n) for some constant c < 1 and large n. In this case T(n) is Θ(f(n)).

VIT/SCOPE/DSA-BCSE202L/M1 82
The Master Theorem…
All these cases are not exhaustive.
In the first case, not only must f(n) be smaller than 𝑛log𝑏 𝑎 , it must be
polynomially smaller.
In the third case, not only must f(n) be larger than 𝑛log𝑏 𝑎 , it also must
be polynomially larger and in addition satisfy the “regularity” condition
that af(n/b) ≤ cf(n)
There is a gap between cases 1 and 2 when f(n) is smaller than 𝑛log𝑏 𝑎
but not polynomially smaller.
Similarly, there is a gap between cases 2 and 3 when f (n) is larger than
𝑛log𝑏 𝑎 but not polynomially larger.
VIT/SCOPE/DSA-BCSE202L/M1 83
The Master Theorem…
If the function f (n) falls into one of these gaps, or if the regularity
condition in case 3 fails to hold, you cannot use the master method
to solve the recurrence.
For example, it is possible for f(n) to be asymptotically larger than
𝑛log𝑏 𝑎 , but not larger by a polynomial factor.
This is true when f(n) = 𝑛log𝑏 𝑎 log n. In this situation, the master
theorem would not apply, and you would have to use another
method to solve the recurrence

VIT/SCOPE/DSA-BCSE202L/M1 84
Example1
𝑇 𝑛 = 9𝑇(𝑛/3) + 𝑛
Solution: a = 9, b = 3, f (n)= n
Here, 𝑛log𝑏 𝑎 = 𝑛log3 9 =𝑛2
Since, 𝑓 𝑛 = Ο 𝑛log3 9−𝜀 = Ο 𝑛 , 𝑤ℎ𝑒𝑟𝑒 𝜀 = 1
Applying case 1 of Master Theorem,
T(n)=Θ 𝑛log𝑏 𝑎 = Θ 𝑛log3 9
= Θ(𝑛2 )

VIT/SCOPE/DSA-BCSE202L/M1 85
Example 2
𝑇 𝑛 = 𝑇(2𝑛/3) + 1
Solution: a = 1, b = 3/2, f (n)= 1
log𝑏 𝑎 log3ൗ 1
Here, 𝑛 =𝑛 2 = 𝑛0 = 1
Since, 𝑓 𝑛 = Ο 𝑛log𝑏 𝑎 = Θ(1)
Applying case 2, the solution to recurrence relation is
T n = Θ 𝑛log𝑏 𝑎 log 𝑛
= Θ(1. 𝑙𝑜𝑔𝑛)
= 𝛩(log 𝑛)

VIT/SCOPE/DSA-BCSE202L/M1 86
Example 3
𝑇 𝑛 = 3𝑇(𝑛/4) + 𝑛𝑙𝑜𝑔𝑛
Solution: a = 3, b = 4, f (n)= nlogn
Here,𝑛log𝑏 𝑎 = 𝑛log4 3 = Ο(𝑛0.793 )
Since, 𝑓 𝑛 = Ο 𝑛log4 3+𝜀 = Ο 𝑛 , 𝑤ℎ𝑒𝑟𝑒 𝜀~0.2
Case 3 applies if we show the regularity condition holds for f(n)
𝑛 𝑛 𝑛 3
𝑎𝑓 =3 log ≤ 𝑛𝑙𝑜𝑔𝑛 = 𝑐𝑓 𝑛 , 𝑓𝑜𝑟 𝑐 = 3/4
𝑏 4 4 4
Applying case 3, the solution to recurrence is
𝑇 𝑛 = Θ 𝑓(𝑛) = Θ(𝑛𝑙𝑜𝑔𝑛)

VIT/SCOPE/DSA-BCSE202L/M1 87
Example 4
T(n) = 2T(n/2)+nlog n.
Solution: a = 2, b = 2, f (n)= nlogn
Even though it appears to have the proper form, Case 3 of master method
does not apply.
f(n) = n log n is asymptotically larger than 𝑛log𝑏 𝑎 = 𝑛log2 2 = n, but not
polynomially larger.
That is, the ratio f(n)/𝑛log𝑏 𝑎 = (nlogn)/n=logn is asymptotically less than
nε for all positive constants ε.
Consequently, the recurrence falls into the gap between case 2 and case 3

VIT/SCOPE/DSA-BCSE202L/M1 88
Practice
1. 𝑇 𝑛 = 3𝑇(𝑛/5) + 8𝑛2
2. 𝑇 𝑛 = 2𝑇(𝑛/2) + 𝑛
3. 𝑇 𝑛 = 4𝑇(𝑛/2) + 𝑛2
4. 𝑇 𝑛 = 8𝑇(𝑛/2) + 𝑛2
5. 𝑇 𝑛 = 7𝑇(𝑛/2) + 𝑛2
6. 𝑇 𝑛 = 4𝑇(𝑛/2) + 𝑛3
7. 𝑇 𝑛 = 3𝑇(𝑛/4) + 𝑛𝑙𝑜𝑔𝑛
8. 𝑇 𝑛 = 4𝑇(𝑛/2) + 𝑛2 𝑙𝑜𝑔𝑛

VIT/SCOPE/DSA-BCSE202L/M1 89
Practice

VIT/SCOPE/DSA-BCSE202L/M1 92