We just worked out a solution to a recurrence relation. We shall now consider a class of recurrence relations that generalizes a recurrence relation and shows how to solve it. The more general class of algorithms is obtained by considering divide-and-conquer algorithms that create recursive calls on q sub problems of size n/2 each, and then combine these solutions in O(n) time. A general recurrence relation used to figure out an algorithm's run time is: T(n) < = qT(n/2) + cn.

We shall now see how to solve the above recurrence by these methods: unrolling, substitution, and partial substitution. Cases q=1 and q>2 are different and shall be considered separately and q=2 as well.

The Case of q>2 Sub problems. Process of figuring out the run time.

• Analyzing the first few levels: At first level of recursion, we have a single problem of size n and takes at most cn time, at the next level we have q problems each of size n/2, each taking cn/2 time at most, and the next level yields q^2 problems of size n/4 each, for a total time of (q^2/4)cn time at most.
• Identifying a pattern: At an arbitrary level j, we have q^j distinct instances, each of size n/(2^j). Thus the total work at each level j is (q/2)^j*cn.
• Summing over all levels of recursion: There are log n levels of recursion, and the total amount of work performed is the sum over all these levels which yields an asymptotic run time of O(n^log q(base 2)). Thus, any function satisfying the recurrence above with q>2 is bounded by this asymptotic run time.

Applying Partial Substitution. Another method of figuring out the recurrence relation. Suppose when q>2, the solution to have the form T(n) < = kn^d for some constants k>0 and d>1. This is quite a general guess, starting with the inductive argument we still reach the same solution. The Case of One Subproblem.

• Analyzing first steps: First level, n problems, taking cn time. Second level, problem of size n/2, which contributes cn/2. and the level after has a prblem of size n/4 that takes cn/4 time.
• Identifying a pattern: at a level j, we have one instance of size n/2^j and contributes cn/2^j to the running time.
• Summing over all recursions we get an asymptotic run time of O(n).

Although the algorithm is performing log n levels of recursion, the overall run time is bounded by O(n). Basically, when q=1, the resulting time is linear

   q=2, the resulting time is O(n log n)
   q>2, Its a polynomial bound with an exponent larger than 1.

A related recurrence: T(n)⇐ 2T(n/2)+O(n^2) The difference between the two recurrence relation is that this one takes quadratic time to combine the subproblems. And the amount of work per level is larger by a factor equal to the input size.

I enjoyed reading through this section and understanding more on finding the recurrence relation of an algorithm. I give it a 9/10 of scale.