Today, we're going to talk about 
recurrence relations, which is a first 
step towards developing mathematical 
models for the performance of computer 
programs s we saw when we covered the 
analysis of Quicksort 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 
hypotheses about the answers that we're 
looking for. 
So, but first of all, what is a 
recurrence? 
Well, it's a simply define. 
It's an equation that defines a sequence 
recursively. 
that's easily understood by computer 
scientists. 
and just as a simple example here's the 
Fibonacci numbers 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 its 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 f0 to be zero and f1 to be one, 
and then insist that the equation hold 
for n greater than or equal to two. 
So, f sub two is zero plus one is one, f 
sub three is one1 plus one is two, and so 
forth. 
We get each term in the sequence by 
adding the previous two. 
So that's 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 and 
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 
of compares taken by quick sort. 
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 c00 as 
specified c1 is two and so forth. 
That's the number of comparisons used by 
quick sort to sort n elements. 
And we remember, we derive the recurrents 
from the program, it's a mathematical 
model of the running time of the program. 
specifically the number of compares taken 
to sort a randomly order sequence of 
array of indistinct elements. 
Now, a common sense rule, anytime you're 
addressed 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, it's even better to do that before 
doing the math as 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 recomputing 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 of 50. 
It's, 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, we'll need a 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 
f of 50, we'll make an array of size 51. 
Set the first two values according to the 
initial conditions. 
and then simply [COUGH] go ahead and 
compute for every 
[COUGH] value in the sequence it's value 
from the previous two values. 
So that's a common sense way to deal with 
any recurrence just use an array. 
now 
[COUGH] what we'll do is maybe a little 
more complete. 
And I, 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 in Java 
courses. 
So if you go to the algorithm's fourth 
edition book site you'll see to get 
started link that you can go ahead and 
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, in a modern approach 
it's, here's this code that goes ahead 
and fills up an array [COUGH] with of 
size n or size max and with the Fibonacci 
numbers. 
but this is a modern approach where we 
use a data type. 
And the client program will go ahead and 
built this array with a constructor and 
then ask for values out of the array. 
Again, this is not the place to talk 
about details of programming with data 
types. 
But this is a very straightforward way to 
approach this problem. 
And the reason that we use it is that we 
can reuse code and, or, or write code 
that we can use for different sequences. 
just by saying that the only way that 
we're going to evaluate what or deal with 
what this sequence is is to use this eval 
function to get out a particular value. 
and then we can write code that 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. 
we, I want to get the first fifteen 
Fibonacci numbers, it prints it out for 
us. 
and you can in your own programming 
environment do whatever you want to to 
get that result and that's an exercise 
worth doing. 
Now more interesting lets 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 the one involving the sun. 
and so this is the corresponding code for 
the Quicksort recurrence. 
to 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 recurrence. 
So the same code will print out the first 
fifteen values of the Quicksort sequence 
in in that way. 
so that's a, a good first start so we can 
get some idea of what these numbers are. 
but actually often what we're want to do, 
and I'll have plenty of examples some 
examples in this lecture is, we just want 
to plot the initial values. 
We want to draw the curve to get some 
idea. 
and so 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, and on the 
x-axis, and the value of the recurrence 
on the y-axis scaled to the largest 
value, 
that's what this 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 
for N log N in this case. 
so, that type of code is a, is a good 
starting point. 
And if you don't want to use my Java code 
it's definitely worth while 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.