Chapter 5.2: Recurrence Relations

If T(n) denotes the running time of a divide-and-conquer algorithm, the it obeys the following recurrence relation: For some constant, c, T(n)=q*T(n/2)+cn when n>2 and T(2)< =c, which I will call (*). We can solve this relation by using unrolling, substitution, and partial substitution.

Unrolling: For the case with q>2 subcases, we start by analyzing the first few levels. At the first level of recursion, we have a single problem of size n, which takes at most cn plus the time spent in all subsequent recursive calls. At the next level, there are q problems, each of size n/2. Each of these take at most cn/2 time for a total of (q/2)cn plus the time of subsequent levels. The next level has q^2 subproblems of size n/4 each, etc. Next we can identify a pattern. At an arbitrary level j, there are q^j distinct subproblems. The total work performed at level j is (q^j)*(cn/(2^j))=(q/2)^j(cn). Then we can find the sum over all levels of recursion. There are log_2(n) levels of recursion, so the total amount of work performed is T(n)< = sum(q/2)^j(cn) from j=0 to j=log_2(n-1). All of this together yields the following: Any function T(.) satisfying (*) with q>2 is bounded by O(n^(log_2(q))). Partial Substitution: Recall that when using partial substitution, you guess the overall form of the solution without pinning down exact values of all the constants and other parameters. Suppose we guess the solution to (*) when q>2 has the form T(n)< =kn^d for some constants k>0 and d>1. We have T(n)< =qT(n/2)+cn and applying the inductive hypothesis to T(n/2) we get T(n)< =qk(n/2)^d+cn = (q/2^d)kn^d+cn. Now we have to choose d so that we get q/2^d=1 and we have to get rid of the cn term. Let d=log_2(q) and suppose we change the form of our guess of T(n) to T(n)< =kn^d-ln. So we have T(n)< =qk(n/2)^d-ql(n/2)+cn = kn^d-(ql/2-c)n. So we choose l so that l=(ql/2-c). For the case when q=1 we can construct a solution by unrolling the recurrence. In doing so, we find that it is bounded by O(n). I would rate this section a 5. I feel like we didn't really cover much of this in class, so it's hard to see how it fits in with the lectures.