Recurrence Tree Method: In this method, we draw a recurrence tree and

calculate the time taken by every level of tree. Finally, we sum the work done at
all levels. To draw the recurrence tree, we start from the given recurrence and
keep drawing till we find a pattern among levels. The pattern is typically a
arithmetic or geometric series.
Step-01:

Draw a recursion tree based on the given recurrence relation.

Step-02:

Determine-
● Cost of each level
● Total number of levels in the recursion tree
● Number of nodes in the last level
● Cost of the last level

Step-03:

Add cost of all the levels of the recursion tree and simplify the expression so obtained in
terms of asymptotic notation.

PRACTICE PROBLEMS BASED ON RECURSION TREE-

Problem-01:

Solve the following recurrence relation using recursion tree method-

T(n) = 2T(n/2) + n

Solution-

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 of size n/2.
● Then, each sub-problem of size n/2 will get divided into 2 sub-problems of size n/4 and so
on.
● At the bottom most layer, the size of sub-problems will reduce to 1.

This is illustrated through following recursion tree-

The given recurrence relation shows-

● The cost of dividing a problem of size n into its 2 sub-problems and then combining its
solution is n.
● The cost of dividing a problem of size n/2 into its 2 sub-problems and then combining its
solution is n/2 and so on.

This is illustrated through following recursion tree where each node represents the cost of
the corresponding sub-problem-
 Step-02:

Determine cost of each level-

● Cost of level-0 = n
● Cost of level-1 = n/2 + n/2 = n
● Cost of level-2 = n/4 + n/4 + n/4 + n/4 = n and so on.

Step-03:

Determine total number of levels in the recursion tree-

● Size of sub-problem at level-0 = n/20
● Size of sub-problem at level-1 = n/21
● Size of sub-problem at level-2 = n/22

Continuing in similar manner, we have-

Size of sub-problem at level-i = n/2i
Suppose at level-x (last level), size of sub-problem becomes 1. Then-
n / 2x = 1
2x = n
 Taking log on both sides, we get-
xlog2 = logn
x = log2n

∴ Total number of levels in the recursion tree = log2n + 1

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-log2n has 2log2n nodes i.e. n nodes

Step-05:

Determine cost of last level-

Cost of last level = n x T(1) = θ(n)

Step-06:

Add costs of all the levels of the recursion tree and simplify the expression so obtained in
terms of asymptotic notation-

= n x log2n + θ (n)
 = nlog2n + θ (n)
= θ (nlog2n)

Problem-02:

Solve the following recurrence relation using recursion tree method-

T(n) = T(n/5) + T(4n/5) + n

Solution-

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-

 The given recurrence relation shows-
● The cost of dividing a problem of size n into its 2 sub-problems and then combining its
solution is n.
● The cost of dividing a problem of size n/5 into its 2 sub-problems and then combining its
solution is n/5.
● The cost of dividing a problem of size 4n/5 into its 2 sub-problems and then combining its
solution is 4n/5 and so on.

This is illustrated through following recursion tree where each node represents the cost of
the corresponding sub-problem-
 Step-02:

Determine cost of each level-

● Cost of level-0 = n
● Cost of level-1 = n/5 + 4n/5 = n
● Cost of level-2 = n/52 + 4n/52 + 4n/52 + 42n/52 = n

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-
● Size of sub-problem at level-0 = (4/5)0n
● Size of sub-problem at level-1 =(4/5)1n
● Size of sub-problem at level-2 =(4/5)2n

Continuing in similar manner, we have-

Size of sub-problem at level-i = (4/5)in
Suppose at level-x (last level), size of sub-problem becomes 1. Then-
(4/5)xn = 1
(4/5)x = 1/n
 Taking log on both sides, we get-
xlog(4/5) = log(1/n)
x = log5/4n

∴ Total number of levels in the recursion tree = log5/4n + 1

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-log5/4n has 2log5/4n nodes

Step-05:

Determine cost of last level-

Cost of last level = 2log5/4n x T(1) = θ(2log5/4n) = θ(nlog5/42)

Step-06:

Add costs of all the levels of the recursion tree and simplify the expression so obtained in
terms of asymptotic notation-
 = nlog5/4n + θ(nlog5/42)
= θ(nlog5/4n)

Master Theorem-
We compare the given recurrence relation with T(n) = aT(n/b) + θ (nklogpn).

Case-01:

If a > bk, then T(n) = θ (nlogba)

Case-02:

If a = bk and
● If p < -1, then T(n) = θ (nlogba)
● If p = -1, then T(n) = θ (nlogba.log2n)
● If p > -1, then T(n) = θ (nlogba.logp+1n)

Case-03:

If a < bk and
● If p < 0, then T(n) = O (nk)
● If p >= 0, then T(n) = θ (nklogpn)

PRACTICE PROBLEMS BASED ON MASTER THEOREM-

Problem-01:

Solve the following recurrence relation using Master’s theorem-

T(n) = 3T(n/2) + n2
Solution-
We compare the given recurrence relation with T(n) = aT(n/b) + θ (nklogpn).
Then, we have-
a=3
b=2
k=2
p=0

Now, a = 3 and bk = 22 = 4.
Clearly, a < bk.
So, we follow case-03.

Since p = 0, so we have-
T(n) = θ (nklogpn)
T(n) = θ (n2log0n)

Thus,

T(n) = θ (n2)

Problem-02:

Solve the following recurrence relation using Master’s theorem-

T(n) = 2T(n/2) + nlogn

Solution-

We compare the given recurrence relation with T(n) = aT(n/b) + θ (nklogpn).

Then, we have-
 a=2
b=2
k=1
p=1

Now, a = 2 and bk = 21 = 2.
Clearly, a = bk.
So, we follow case-02.

Since p = 1, so we have-
T(n) = θ (nlogba.logp+1n)
T(n) = θ (nlog22.log1+1n)

Thus,

T(n) = θ (nlog2n)

Problem-03:

Solve the following recurrence relation using Master’s theorem-

T(n) = 2T(n/4) + n0.51

Solution-

We compare the given recurrence relation with T(n) = aT(n/b) + θ (nklogpn).

Then, we have-
a=2
b=4
k = 0.51
 p=0

Now, a = 2 and bk = 40.51 = 2.0279.

Clearly, a < bk.
So, we follow case-03.

Since p = 0, so we have-
T(n) = θ (nklogpn)
T(n) = θ (n0.51log0n)

Thus,

T(n) = θ (n0.51)

Problem-04:

Solve the following recurrence relation using Master’s theorem-

T(n) = √2T(n/2) + logn

Solution-

We compare the given recurrence relation with T(n) = aT(n/b) + θ (nklogpn).

Then, we have-

a = √2
b=2
k=0
p=1

Now, a = √2 = 1.414 and bk = 20 = 1.

 Clearly, a > bk.
So, we follow case-01.

So, we have-
T(n) = θ (nlogba)

T(n) = θ (nlog2√2)
T(n) = θ (n1/2)

Thus,

T(n) = θ (√n)

Problem-05:

Solve the following recurrence relation using Master’s theorem-

T(n) = 8T(n/4) – n2logn

Solution-

● The given recurrence relation does not correspond to the general form of Master’s
theorem.
● So, it can not be solved using Master’s theorem.

Problem-06:

Solve the following recurrence relation using Master’s theorem-

T(n) = 3T(n/3) + n/2

Solution-
● We write the given recurrence relation as T(n) = 3T(n/3) + n.
● This is because in the general form, we have θ for function f(n) which hides constants in
it.
● Now, we can easily apply Master’s theorem.

We compare the given recurrence relation with T(n) = aT(n/b) + θ (nklogpn).

Then, we have-
a=3
b=3
k=1
p=0

Now, a = 3 and bk = 31 = 3.
Clearly, a = bk.
So, we follow case-02.

Since p = 0, so we have-
T(n) = θ (nlogba.logp+1n)
T(n) = θ (nlog33.log0+1n)
T(n) = θ (n1.log1n)

Thus,

T(n) = θ (nlogn)

Problem-07:

Form a recurrence relation for the following code and solve it using Master’s theorem-
● We write a recurrence relation for the given code as T(n) = T(√n) + 1.
● Here 1 = Constant time taken for comparing and returning the value.
● We can not directly apply Master’s Theorem on this recurrence relation.
● This is because it does not correspond to the general form of Master’s theorem.
● However, we can modify and bring it in the general form to apply Master’s theorem.

Let-
n = 2m ……(1)
Then-
T(2m) = T(2m/2) + 1

Now, let T(2m) = S(m), then T(2m/2) = S(m/2)

So, we have-
S(m) = S(m/2) +1
Now, we can easily apply Master’s Theorem.

We compare the given recurrence relation with S(m) = aS(m/b) + θ (mklogpm).

Then, we have-
a=1
b=2
k=0
p=0
 Now, a = 1 and bk = 20 = 1.
Clearly, a = bk.
So, we follow case-02.

Since p = 0, so we have-
S(m) = θ (mlogba.logp+1m)
S(m) = θ (mlog21.log0+1m)
S(m) = θ (m0.log1m)

Thus,
S(m) = θ(logm) ……(2)

Now,
● From (1), we have n = 2m.
● So, logn = mlog2 which implies m = log2n.

Substituting in (2), we get-

S(m) = θ(loglog2n)
Or

T(n) = θ (loglog2n)