RECURRENCE RELATION

Master Theorem

Not all the recurrences can be solved using the Master Theorem, but it still solves a large family of recurrences. Here is the classification of recurrences which can be solved using this theorem.

• It solves the recurrences of form T(n) = aT(n/b) + f(n).
• a should be greater than or equal to 1. Which means that the problem is at least reduced to a smaller sub problem once. At least one recursion is needed
• b should be greater than 1. Which means at every recursion, the size of the problem is reduced to a smaller size. If b is not greater than 1, that means our sub problems are not of smaller size.
• f(n) must be positive for relatively larger values of n.

Basis of Master Theorem

Let us consider the below tree:

Lets say we have a problem of size n to be solved. At each step the problem can be divided into a sub problems and each sub problem is of smaller size, where the size is reduced by a factor of b.

The above statement in simple words means that a problem of size n can be divided into a sub problems of relatively smaller sizes n/b.

Also, the above diagram shows that at the end when we have divided the problems multiple times, each sub problem would be so small that it can be solved in constant time.

Some Deductions

Now, what can we say about the height of the tree?

Let us say that H is the height of the tree, then H = logbn.

Here is a simple deduction, the problem size reduces by a factor b at each level. So it would take logbn levels to reduce it to a problem of size 1 and it cannot be divided further.

What is the number of leaves in the tree?

The relationship between height of a tree and the number of leaf nodes is as follows:
number of leaves = branching_factorheight.

Hence the number of leaves would be aH. Replacing H in this equation, we would get the number of leaves = alogbn.

By the following properties of logarithms we can rearrange the formula.
NlogkM = MlogkN. Therefore the number of leaves = nlogba.

Finding the work done at each level in the tree

• Total work done at Level 1 : f(n)
• Total work done at Level 2 : a * f(n/b)
• Total work done at Level 1 : a * a * f(n/b2)
• Total work done at last Level : number of leaves * θ(1). This equals to nlogba

Note : In case the above calculations do not make much sense, I would advice you to understand these by redoing it for a simple binary tree.

Three cases of Master Theorem

With the help of the above deductions, we are in a shape to discuss the three cases of the Master Theorem.

1. Now let us assume that the cost of operation is increasing by a significant factor at each level and by the time we reach the leaf level the value of f(n) becomes polynomially smaller than the value nlogba. Then the overall running time will be heavily dominated by the cost of the last level. Hence T(n) = θ(nlogba)

 

1. Let us assume that the cost of the operation on each level is roughly equal. In that case f(n) is roughly equal to nlogba. Hence, the total running time would be f(n) times the total number of levels.
   T(n) = θ(nlogba * logk+1n) where k can be >=0. Where logk+1n would be the height of a tree for k >= 0

 

1. Let us assume that the cost of the operation on each level is decreasing by a significant factor at each level and by the time we reach the leaf level the value of f(n) becomes polynomially larger than the value nlogba. Then the overall running time will be heavily dominated by the cost of the first level. Hence T(n) = θ(f(n))

.

This is the simplest way how we can understand the Master Theorem.

Few Examples of Solving Recurrences – Master Method

Now that we know the three cases of Master Theorem, let us practice one recurrence for each of the three cases.

Example for Case 1

Assume the recurrence equation is T(n) = 4T(n/2) + n

Let us compare this recurrence with our eligible recurrence for Master Theorem T(n) = aT(n/b) + f(n).
We find that a = 4, b = 2 and f(n) = n
Let us find out nlogba, which is the work done at last level, using the above values. It is equal to nlog24, which is equal to n2.

Now let us compare the work done at first and last level. Which means comparing f(n) with nlogba.
f(n) = n and nlogba = n2.

We know that n2 is significantly greater than n for larger n. Hence, it is the first case of Master Theorem. Therefore the solution to this recurrence is θ(nlogba). So T(n) = θ(n2).

Example for Case 2

Assume the recurrence equation is T(n) = 4T(n/2) + n2

Let us compare this recurrence with our eligible recurrence for Master Theorem T(n) = aT(n/b) + f(n).
We find that a = 4, b = 2 and f(n) = n2
Let us find out nlogba, which is the work done at last level, using the above values. It is equal to nlog24, which is equal to n2.

Now let us compare the work done at first and last level. Which means comparing f(n) with nlogba.
f(n) = n2 and nlogba = n2.

We know that n2 is equal to n2. Hence, it is the second case of Master Theorem. Therefore the solution to this recurrence is θ(nlogba * logk+1n). So T(n) = θ(n2log2n).

Example for Case 3

Assume the recurrence equation is T(n) = 4T(n/2) + n3

Let us compare this recurrence with our eligible recurrence for Master Theorem T(n) = aT(n/b) + f(n).
We find that a = 4, b = 2 and f(n) = n3
Let us find out nlogba, which is the work done at last level, using the above values. It is equal to nlog24, which is equal to n2.

Now let us compare the work done at first and last level. Which means comparing f(n) with nlogba.
f(n) = n3 and nlogba = n2.

We know that n3 is significantly greater than n2 for larger n. Hence, it is the third case of Master Theorem. Therefore the solution to this recurrence is θ(f(n)), which is equal to n3.