Solving Recurrences - Master method

Solving Recurrences - Master method

Methods to solve the recurrences to get bounds on the runtime are :

1. Substitution method
2. Recursion tree
3. Master theorem

3. The master method for solving recurrences

The master theorem is a formula for solving recurrences of the form T(n) = aT (n/b)+f(n), where a ≥ 1 and b > 1 and f(n) is asymptotically positive. (Asymptotically positive means that the function is positive for all sufficiently large n.)

The master method depends on the following theorem.

In each of the three cases, we compare the function f(n) with the function n^log_b^a. The larger of the two functions determines the solution to the recurrence.

If, as in case 1, the function n^log_b ^a is the larger, then the solution is T(n) = θ(n^log_b ^a).

If, as in case 2, the two functions are the same size, we multiply by a logarithmic factor, and the solution is T (n) = θ(n^log_b ^a lg n) = θ(f (n) lg n).

If, as in case 3, the function f (n) is the larger, then the solution is T (n) = θ(f(n)).

Using the master method

To use the master method, simply determine the case (if any)  to be applied of the master theorem and write down the answer.

Examples for above three cases are given below :

Solving Recurrences - Recursion Tree method

Solving Recurrences - Recursion Tree method

Methods to solve the recurrences to get bounds on the runtime are :

1. Substitution method
2. Recursion tree
3. Master theorem

2. The recursion-tree method for solving recurrences

A recursion tree is a tree where each node represents the cost of a certain recursive sub-problem. Then you can sum up the numbers in each node to get the cost of the entire algorithm.

A recursion tree is best used to generate a good guess, which you can then verify by the substitution method. 

Example:

 Consider a recurrence: 

Drop the floors and write a recursion tree for  T(n) = 3T(n /4) + cn².

For convenience, assume that n is an exact power of 4 so that all subproblem sizes are integers.

Part (a) of the figure shows T(n), which we expand in Part (b) into an equivalent tree representing the recurrence. The cn² term at the root represents the cost at the top level of recursion, and the three subtrees of the root represent the costs incurred by the subproblems of size n/4.

Part (c) shows this process carried one step further by expanding each node with cost T(n/4) from Part (b). The cost for each of the three children of the root is c(n/4)².

Because subproblem sizes decrease by a factor of 4 each time we go down one level, we eventually must reach a boundary condition.

The subproblem size for a node at depth i is n=4ⁱ. Thus, the subproblem size hits n =1 when n / 4ⁱ = 1 or, equivalently, when i = log₄ n. Thus, the tree has log₄ n +1 levels (at depths 0,1,2,.........,log₄ n).

Next we determine the cost at each level of the tree. Each level has three times more nodes than the level above, and so the number of nodes at depth i is 3ⁱ. And because subproblem size reduce by a factor of 4 for each level we go down from the root, each node at depth i, for i = 0,1,2,…….,log₄ n-1, has a cost of c(n/4ⁱ )².

Therefore the total cost over all nodes at depth i, for i = 0,1,2,…..,log₄ n -1, is 

3ⁱ c(n/4ⁱ )² = (3 /16)ⁱ c n².

The bottom level, at depth log₄ n, has 3^log₄ ⁿ = n^log₄ ³ nodes, each contributing cost T(1) for a total cost of n^log₄ ³T(1), which is θ(n^log₄ ³), since we assume that T(1) is a constant.

Now we add up the costs over all levels to determine the cost for the entire tree:

Can be written as,

Thus, we have derived a guess of T (n) = O(n²) .

Now use the substitution method to verify the guess correctness.

T (n) = O (n²) is an upper bound for the recurrence 

We want to show that T (n) ≤ dn² for some constant d > 0.

Using the same constant c > 0 as before, we have

where the last step holds as long as d ≥ (16/3)c.(when c =(3/16)d,  i.e. d ≥ (16/3)c).

Solving Recurrences - Substitution method

Solving Recurrences - Substitution method

Methods to solve the recurrences to get bounds on the runtime are :

1. Substitution method
2. Recursion tree
3. Master theorem

1. Substitution method

The substitution method for solving recurrences comprises two steps:

1. Guess the form of the solution.

2. Use mathematical induction to find the constants and show that the solution works.

This method is powerful, but we must be able to guess the form of the answer in order to apply it. The substitution method can be used to establish either upper or lower bounds on a recurrence.

Example: Recurrence: 

We guess that the solution is T(n) = O(n log n). So we must prove that T(n) <= c  n log n  for some constant c.

As our inductive hypothesis, we assume T(n) = c n log n for all positive numbers less than n.

and

Now we need to show the base case. This is tricky, because if T(n) ≤ cn log n, then T(1) ≤ 0,

which is not a thing( T(1) = 1 given)

So revise our induction so that we only prove the statement for n ≥2, and the base cases of the induction proof are n = 2 and n = 3.

n = 2 and n = 3 is choose as base cases because when the recurrence formula is expanded , we will always go through either n = 2 or n = 3 before we hit the case where n = 1.

Plugging the numbers into the recurrence formula, we get 

T(2) = 2T(1) + 2 = 4 and

T(3) = 2T(1) + 3 = 5. 

So now we just need to choose a c that satisfies those constraints on T(2) and T(3). 

We can choose c = 2, because 4 ≤ 2 .2 log 2 and 5 ≤2 .3 log 3.

Therefore, we have shown that T(n) ≤ 2n log n for all n ≥ 2, so T(n) = O(n log n).