Today we're going to talk about recurrence relations. Which is a first step towards developing mathematical models for the performance of computer programs, as we saw when we covered the analysis of quick sort in the last lecture. To begin we're going to look at the idea of using the computer to compute values of recurrence relations. This is very important for us as unlike many other mathematical disciplines we have the ability to be able to quickly check our answers and maybe develop hypothesis about the answers that we're looking for. So but first of all what is recurrence? Well it’s a simply defined it’s an equation that defines a sequence recursively. Well that’s easily understood by computer scientist and just as a simple example here’s Fibonacci number recurrence which is familiar to mathematicians as well So the recurrence relation is F sub N = F sub N -1 + F sub N -2, so that's defined recursively. Each term in the sequence is defined in terms of previous terms in the sequence. But it's very important as every programmer knows in a recursive program you need to specify the initial conditions. Also in a recurrence relation, you need to carefully specify initial conditions and make sure that things are defined for all values of N. In the case of the Fibonacci numbers we define f 0 to be 0 and f 1 to be 1. And then insist that the equation hold for n greater than or equal to 2. So f sub 2 is 0 + 1 is 1. f sub 3 is 1 + 1 is 2, and so forth. We get each term in the sequence by adding the previous two. So that's an example of a recurrence relation. So now the question that naturally comes up is, if we're given the recurrence relation, can we come up with a simple formula for describing fN as a function of N, as a simple function of N. That's the kind of question that we're going to be addressing. Now as we saw in the last lecture, recurrences directly model costs in programs. For example, we talked about Quicksort. And it's a much more complicated recurrence. But it still has the same property that every term in the sequence, in this case, the sequence defines the running time of Quicksort or the number compares taken by Quicksort. Every term in the sequence is defined in terms of earlier terms in the sequence. In this case, the result is not integers and you can work out that. C zero zero as specified. C one is two. And so forth, that's the number of comparisons used by quick sort to sort in elements. And we remember, we derived the occurrence from the program. It's a mathematical model of the running time in a program. Specifically the number of compares taken to sort a randomly ordered sequence of array of indistinct elements. Now, a common sense rule anytime you're faced with a recurrence nowadays is just to use the computer to compute values to see if you can understand what the values are and what's going on. It's even better to do that before doing the math because it might tell you something that might be difficult to discover with math and it's so easy to do. So first thing you might say is why not use a recursive program. Well we teach now in every elementary programming course that you don't want to do this. It's a very bad idea to try to compute values of a recurrence like this with a recursive program because it takes exponential time. That is, to compute f of 50, we have to compute 49 and 48. To compute 49, 48 and 47 and so forth. And if you look at this table, you'll see that we're re-computing values all the time. F of 48 twice, F of 47 three times, F of 46 five times and so forth. Actually, it takes exponential time to compute this, so it's not going to complete even for F 50. It's much much too slow. So it would be nice to think about using a recursive program, but we don't do that in practice. Instead what we do is save all the values in an array and so we'll need an array entry for every value that we want to compute. But nowadays that's no problem. So in this case if you want to compute after 50 we make it a ray of size 51. Set the first two values according to the initial conditions and then simply go ahead and compute for every value in the sequence. Its value from the previous two values. So that's a common sense way to deal with any recurrence. Just use an array, now what we'll do is maybe a little more complete. And I don't want to make this a course on modern programming techniques. But I might as well use modern code so that we can leverage off of all the code that we've developed for our algorithms in Introduction to Programming and Java courses. So if you go to the algorithms, 4th edition book site You'll see to get started on [INAUDIBLE] that you can go ahead use to download some standard library packages that are available for average programmers to write these kinds of programs, using a modern model. This is not required, but many people will be familiar with this model. So it's the one that I'm going to use for the code that I cover in this course. And this code is easily translated to other environments and languages. So I'm not going to dwell on that. So nowadays, in a modern here's this code that goes ahead and fills up an array of size N or size max with the Fibonacci numbers. But this is a modern approach where we use a data type in the client program. We'll go ahead and build this array with a constructor. And then I ask for values out of the array. Again, this is not the place to talk about the details of programming with data types, but this is a very straight forward way to approach this problem. And the reason that we use it is that we can, Reuse code, or write code that we could use for different sequences just by saying that the only way that we're going to evaluate or deal with what the sequence is it to use this eval function to get out a particular value. And then we can write code that now will print out values for any sequence, so this code, for example. So again, in this case, with this code, it's not that much code, I want to get the first 15 Fibonacci numbers, that prints it out for us. And you can, in your own programming environment, do whatever you want to, to get that result. And that is an exercise worth doing. Now more interesting. Let's look at the Quicksort recurrence. Now remember, we did some algebra to show that we can make the Quicksort recurrence, a very simple linear recurrence, rather than one involving the sum, and so this is the corresponding code for the Quicksort recurrence. Using that version of the recurrence, we can [COUGH] In the constructor, create an array, fill it up with the first N values, just using that recurrence. So it's just dividing by N. And then, eval will give us the value of that occurrence. So the same code will print out the first 15 values of the quick sort sequence in that way. So that's a good first start. So we can get some idea of what these numbers are. But actually, often what we want to do, and I'll have plenty of examples in this lecture is We just want to plot the initial values, we want to draw the curve to get some idea. This code here uses our standard library for drawing things within a window on your computer to do the plot and I'll have some examples later on. That use this kind of code to just draw the value of each recurrence for n on the x axis, and the value of recurrence on the y axis scaled to the largest value. That's what this code does. So in the case of quicksort if we use a call on this show method instead of printing out the values then you get the curve like that which is the curve for end-login in this case. So, that type of code is a, is a good starting point in, if you don't want to use my java code it's definitely worthwhile for you to use whatever programming environment you're comfortable with to be sure that you can compute values of any recurrence efficiently and also to be able to develop plots like this. And you'll get a good feeling for why we want to do that in just a minute. So that's computing values of a recurrence.
