Tech Wave

I was forced to write a paper for English class called a process paper. I decided to write a walk through on how to do recurrence relation analysis’ because the literature that we were given did not make it easy to understand the process. I feel that my essay is a much better source for teaching someone how these work.  I hope this is a useful resource for all and I release this for any educational use as long as I still receive credit as the author.

word document version

——-HTML version——-

How to perform a recurrence relations analysis via backward substitution.

As many who have taken algorithms may know, the process for performing a recurrence relations analysis is not explained well in the required literature.  This is made more difficult by the literatures poor assumption that everyone reading the book is a mathematician.  My goal is to break this convoluted process into smaller pieces so that anyone studying algorithms can master this essential analysis tool. This document explains how to make a recurrence relation formula from a recursive algorithm, and then show how a pattern can be determined through backward substitution using the formula.  We will then utilize the pattern along with the end condition of the algorithm to solve for n and i. This will be followed by some simple algebra, which we use to determine the final growth rate of the algorithm.

A recurrence relation is a formula used to determine the rate of growth for a recursive algorithm.  In the case of a regular algorithm you would use summation to calculate this, but recursive algorithms require special methods due to their nature.  The first step is to determine the main operation in the algorithm and determine how many times it occurs per method call. In figure 1a the main operation is multiplication, and that operation occurs twice per call. The last part of determining the recurrence relation is finding the end condition and its cost.  In Figure 1a’s case, the end condition is where n=1 and the cost is zero, since the end condition does not perform any multiplication. With this, you have now constructed the recurrence relation for the algorithm and are ready to solve for its rate of growth.  The recurrence relation for figure 1a should be written as:  f (n) = f (n-1) + 2, f (1) = 0. The part of the equation that is before the comma is the cost per reoccurrence, and the part after the comma are the end condition and its cost.

Now this is where backwards substitution comes in as the next step.  As you can see, the formula references itself, and we use this to our advantage through backwards substitution. Say we try to figure out the above formula for n-1 instead of n, what would that change?  In this case the formula should look like line 2 of figure 1b. This process should be repeated two times to determine the pattern, or more if needed.  Now we use the formulas that we just defined to replace the values in f (n), as in figure 1b line 4. We then continue to substitute the values upwards until there is enough to establish a pattern, as in figure 1b line 5. We then compress the formula down like figure 1b line 6 shows. Now that we have gotten this far we should be able to establish a pattern in terms of i. An example of this is figure 1b line 7. Everywhere that we see a number increased by a steady amount we can put i as a multiplier of that steady amount.  We can now use this in combination with the end condition to complete the process.

The use of the end condition is crucial in this step, because it is the source for the right side of the equation. First we take the inside of the patterns function, illustrated in figure 1c line 1 with a single underline, and place it on one side of our new equation. We then place the value for the equation that returns the end condition on the other side of the equation, which is illustrated in figure 1c line 1 with double underlines. We can now find out what value n needs to be in order for the pattern equation to fulfill the end condition. In this case n has to equal 1+ i for n-i to return 1.  I usually solve for i as well, because it helps finish off the formula nicely. We then insert the value of n into the pattern formula as shown in figure 1c line 4. We continue to process the formula as if it were any other algebra formula demonstrated in figure 1c lines 5-7. Finally we substitute in the value of i so that n is the only variable in the formula, which is demonstrated on lines 8-9 of figure 1c. After you have completed this process you have the growth rate for the recursive algorithm in question. To verify correctness I usually run through the original recurrence relation formula with some small numbers, and then compare those numbers with the numbers I get using the new equation. If the process was done correctly you should have exactly the same numbers from both equations.

Although, this process can be hard to follow, and even harder to learn if you don’t know what is going on. This paper has gone about showing you how to understand the most crucial and difficult steps in the backwards substitution process. First we showed you how to create a recurrence relation formula which identifies the cost of the algorithm. Second we showed you how to create a pattern from the recurrence relation formula using backwards substitution. Then with that pattern you were able to solve for n and i. We then used those values along with some simple algebra to solve for the growth rate of the algorithm. This paper brings the process down to its core pieces and in doing so makes it possible for even a high school level math student to use the process.