Recursions "Review"

Question 1

What are three methods for solving a recursion?

Answer 1

1) Substitution: Guess a bound, then using induction to prove our guess correct.
2) Recursion-tree: Convert the recurrence into a tree whose nodes are the costs incurred at different levels of the recursion. Use techniques for bounding summations to solve the recurrence.
3) Master method: provides bounds for recurrences of the form T(n) = a * T(n/b) + f(n).

Question 2

Recursion tree method

Answer 2

To solve a recursion using a recursion tree, we want to find the cost of each subproblem and sum them up. Start with the root, T(n). If our algorithm divides this into two subproblems of size n/2, then T(n) has two children, each equal to T(n/2). We do this for each subproblem until they are of a size small enough to reach the base case.

Let c be the cost of an operation on a single input element. Then T(n) = cn, T(n/2) = cn/2, etc. Sum each level of the tree to get the cost of that level (in this case each would sum to cn). Then we need to multiply by the number of levels. Because it’s a binary tree, this will be lg(n) + 1. cn(lg(n) + 1) = cnlg(n) + cn. Dropping the constant terms gives us a runtime of Theta(nlg(n))

Question 3

Substitution method

Answer 3

Say we have a a recurrence T(n) = 2T(floor(n/2)) + n and we believe it to be O(nlg(n)). The substitution method requires that we prove T(n) <= cnlg(n) for some c > 0.

First, assume the bound holds for all m < n, in particular m = floor(n/2), implying that T(floor(n/2)) <= cfloor(n/2)lg(floor(n/2)). Then substitute this into our recurrence relation T(n) <= 2(cfloor(n/2)lg(floor(n/2)) + n and simplify T(n) <= cn*lg(n) for c >= 1.

Next, show that the solution holds for boundary conditions (something like T(1) = 1). This is often a tricky part. In this example, T(1) <= c1lg(1) = 0, which contradicts T(1) = 1. When this happens, we have to extend the boundary conditions, distinguishing between the base case of recurrence (n=1) and base case of inductive proof (n=2 and n=3). This new base case should let us write the inductive proof without referring to T(1).

Question 4

Master method

Answer 4

Solves recurrences of the form T(n) = a*T(n/b) + f(n) where a >= 1, b > 1, and f(n) is an asymptotically positive function. This form describes the running time of a problem that we divide into subproblems of size n/b. f(n) is the cost of dividing the problem into subproblems and re-combining them.

Basically, it’s good for divide and conquer recurrences!

Recurrences of this form often satisfy one of the three following regimes, based on how the work to split/recombine the problem f(n) relates to the critical exponent:
c_crit = log_b(a) = log(#number of subproblems) / log(relative problem size)

1) Work to split/recombine a problem is dwarfed by subproblems, i.e., the recursion tree is leaf-heavy
2) Work to split/recombine a problem is comparable to subproblems
3) Work to split/recombine a problem dominates subproblems, i.e., the recursion tree is root-heavy

Question 5

Describe the form of the recurrence for which we use the master theorem

Answer 5

The master theorem is for divide and conquer, i.e., recurrences of the form T(n) = a*T(n/b) + f(n) where…

• a >= 1
• b > 1
• f(n) is an asymptotically positive function

This form describes the running time of a problem that we divide into subproblems of size n/b. f(n) is the cost of dividing the problem into subproblems and re-combining them.

Question 6

What is the critical exponent in the master theorem?

Answer 6

c_crit = log_b(a) = log(#number of subproblems) / log(relative problem size)

Question 7

What are the three regimes of the master theorem?

Answer 7

1) Work to split/recombine a problem is dwarfed by subproblems, i.e., the recursion tree is leaf-heavy. f(n) = O(n^c) where c < c_crit (upper-bounded by a lesser exponent polynomial)
2) Work to split/recombine a problem is comparable to subproblems. f(n) = Theta(n^c_crit log^k n) for k >= 0 (rangebound by the critical-exponent polynomial, times zero or more optional
logs)
3) Work to split/recombine a problem dominates subproblems, i.e., the recursion tree is root-heavy. f(n) = Theta(n^c) where c > c_crit (lower-bounded by a greater-exponent polynomial)

Question 8

What are the solutions for each of the three regimes of the master theorem?

Answer 8

1) Work to split/recombine a problem is dwarfed by subproblems, i.e., f(n) = O(n^c) where c < c_crit

Solution: T(n) = Theta(n^c_crit)

2) Work to split/recombine a problem is comparable to subproblems, i.e., f(n) = Theta(n^c_crit log^k n) for k >= 0

Solution: T(n) = Theta(n^c_crit * log^(k+1) n)

3) Work to split/recombine a problem dominates subproblems, i.e., f(n) = Theta(n^c) where c > c_crit

Solution: T(n) = Theta(f(n)) (requires additional condition, but usually holds)