Class 3: Recurrences

 

A recurrence is an equation that describes a function in terms of its value on smaller inputs. For example, the worst-case running time of the merge-sort is described as follows:

 

                        Q(1), if n = 1

T(n) =

                        2T(n/2)+ Q(n)

 

Solving a recurrence means obtaining asymptotic Q or O bounds on the solution. We consider the following methods:

 

·        Substitution method: guessing a bound, and then using mathematical induction to prove its correctness.

·        Recursion-tree method: converting the recurrence into a tree, whose nodes represent costs incurred at various levels of the recursion.

·        Master method: provides bounds for recurrences of the form T(n) = aT(n/b) + f(n).

 

The substitution method

 

This method involves two steps:

 

 

The substitution method can be used to establish either upper or lower bounds on a recurrence. For example, determine an upper bound on:

 

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

 

We guess that the solution is T(n) = O(nlgn). We need to prove that T(n) <= cnlgn for an appropriate choice of c>0. We start by assuming that this bound holds for floor(n/2), i.e.

 

T(n/2) <= c n/2 lg(n/2)

 

We now substitute in the recurrence as follows

 

T(n) = 2T(n/2) + n <= 2 c floor(n/2) lg(floor(n/2)) + n <=

c n lg(n/2) + n =

c n (lgn – lg2) + n =

c n lgn –cn + n <= c n lgn for c>= 1

 

To prove by induction we also need to show that the expression holds for the boundary conditions. In our case we can take advantage of asymptotic notation that requires us to prove T(n) <= c n lgn for n>n0. We can simply choose n0 = 2 and derive from the recurrence T(2) = 2T(1)+2 = 4. Hence we need to prove T(2) <= c2lg2 = 2c, which is true for c>= 2.

 

The recursion-tree method

 

The substitution method can provide a quick proof that a solution to the recurrence is correct, however, it may be difficult to find a good guess. Drawing out a recursion tree is a straightforward way to devise a good guess:

 

·        Each node represents the cost of a single subproblem.

·        The sum of the costs within each level gives a per-level cost.

·        The sum of all per-level costs gives an estimate of the total cost.

 

Example: find the upper bound for

 

T(n) = 3T(floor(n/3)) + Q(1)

 

We know that floors and ceilings are insubstantial, so we create the recursion tree for

 

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

 

a) One step:

 

            c

 

T(n/3)   T(n/3) T(n/3)

 

 

b) Two steps:

 

                                                c

 

                        c                      c                      c

 

T(n/9)   T(n/9)            T(n/9)            ...

 

c) Reaching the boundary condition occurs at n/3^i = 1 => 3^i = n => i=log3 n. Hence the recursion tree has log3 n levels:

                                                c                                                          .........            c         

 

                                    c            c            c                                              .........            3c

 

T(n/9)            T(n/9)                                                               .........            9c

 

...

 

T(1) ... T(1) ...                                                                                      ........            3log3n=n

 

 

Now we add the cost of all levels:

 

T(n) = c + 3c + 9c + ... + n = c (3log3n-1 – 1)/(3-1) + n = O(n)

 

Now we use substitution method to prove our hypothesis.

 

We need to show T(n) <= d n - b for some constant d and b>0

 

Assume T(n/3) <= d (n/3) - b, then

 

T(n) = 3 T(n/3) + c <= 3 (d (n/3) – b) + c = dn – 3b + c = (dn – b) + (c-2b) <= dn – b

 

for b >= c/2

 

Note that, the recursive assumption is stronger than O(n), which certainly makes the original assumption true.

 

The master method

 

The method provides an analytic solution for 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.

 

Theorem 4.1 (Master theorem)

 

Let a >= 1 and b>1 be constants, let f(n) be a function, and let T(n) be defined on nonnegative integers by the recurrence

 

T(n) = a T(n/b) + f(n)

 

where we interpret n/b to mean either floor(n/b) or ceil(n/b). Then T(n) can be bounded asymptotically as follows.

  1. If f(n) = O(n^(logba-e)) for some constant e>0, then T(n) = Q( n^logba).
  2. If f(n) = Q( n^logba), then T(n) = Q( n^logba lgn).
  3. If f(n) = W(n^(logba+e)) for some constant e>0, and if a f(n/b) <= c f(n) for some constant c<1 and all sufficiently large n, then T(n) = Q(f(n)).

 

In all three cases we are comparing the recursion division cost function with the function n^logba. Intuitively, the solution to the recurrence is determined by the larger of the two functions.

 

It is important to realize that the three cases do not cover all the possibilities for f(n). There's a gap between 1 and 2, and 2 and 3. When the function falls in one of these gaps, or if the regularity condition fails to hold, the master method cannot be used to solve the recurrence.