And next it will be worthwhile to 
consider a detailed example to set the 
stage by illustrating the kinds of 
mathematical techniques that, that we 
were using. 
So let's use a classic application for 
the analysis of algorithms. 
and a very ubiquitous, structure in 
computer algorithms and implementations 
is a binary tree. 
And so, one question that arises is, how 
many bits do you need to represent a 
binary tree with N internal node? And 
there's many applications of this for 
example there's data compression 
algorithms that involve building a code 
that's represented with a binary tree and 
then transmitting the binary tree. 
And you want to do it with the least 
number Bits 
So the answer which is kind of direct 
from information theory is that if you 
know the number of different binary trees 
with N internal nodes then you need log 
base 2 of that many bits. 
because otherwise, you couldn't 
distinguish between, there'd be two trees 
you couldn't distinguish between. 
So, you need at least log base to TN, 
where TN is the number of binary trees, 
with N internal nodes. 
so then the question returns the reduces 
immediately to accounting question. 
How many binary trees are there within 
internal nodes? so that's a classic 
application of analysis of algorithms. 
We have this practical problem and we, 
and we want to solve this accounting 
problem. 
So the first step in, in the classic 
analysis of algorithms is to go ahead and 
develop a recurrence relation. 
A binary tree is a recursive structure 
where you have a node that has exactly 2 
sub trees, 
a left sub tree and a right sub tree and 
if there's k nodes on the left then 
there's n-1k nodes on the right. 
So we can write down this mathematical 
recurrence relation on the bottom left. 
There. 
T sub N is equal to the sum for all K 
between 0 and N-1 of the product of these 
two. 
You can have any tree on the left, and 
any tree on the right. 
and then we add a chronic of delta, for 
zero, because we say there's exactly one 
binary tree with zero nodes to make the 
recurrence work. 
And over in the right here is this small 
case, is it's showing there's one tree 
with one node, two trees with two nodes, 
three trees with five nodes, 14 trees 
with four nodes and so forth. 
So that's the first step, develop a, a 
recurrence relation. 
Now the next step is to introduce what's 
called a generating function to try and 
solve that recurrence relation. 
Use that mathematical relationship to try 
to get an explicit expression for the 
number of binary trees of n nodes. 
and the generating function is just sum 
for all n. 
the number of trees with n nodes times z 
to the n, 
Where z's a, a free variable. 
T of z is defined to be the sum for all n 
of t sub nz to the n. 
and, so, on the right hand side. 
we have a double sum. 
Sum for N greater or equal 0 and then the 
recurrence, TKTN minus k, sub [INAUDIBLE] 
k times Z of N. 
and then the delta N0 just reduces to a 
1. 
so we, now we have an expression for T of 
Z. 
And what we're going to do is manipulate 
the sums on the right hand side, to 
express them, in terms of T of Z. 
And the way to do that, is to switch the 
order of summation, put the sum on n 
inside the sum of k outside. 
So, it's the sum all positive k, sum and 
bigger than k, tn minus k, tn, tk, tn 
minus 1, minus k, z to n. 
And then the next thing you can do is 
change n to n plus k plus 1. 
and that will allow us to separate the 
sums. 
so TN minus 1 minus K becomes t sub n, z 
to the n, becomes, Zn plus k plus 1. 
And now that allows us to distribute and 
separate the sums. 
So t of z equals 1 plus z, 
Sum on k, TkZ to the K, sum on N, TNZ ^ 
N, and both of those are nothing more 
than T of Z so we have a, an explicit 
relationship on the generating function. 
T of Z equals 1 + ZT of Z squared. 
So starting with the recurrence, we end 
up with a functional equation that the 
generating function must satisfy. 
That's the second step in classic 
analysis of algorithms. 
Now, the third step is to take that 
functional equation and use it to extract 
the coefficients, to tell us what TN is. 
That's what we're after. 
So the functional equation is from the 
last slide, T of Z is 1 plus ZT of Z 
squared. 
we can use a quadratic formula to solve 
that. 
and so just, it's just a quadratic in T 
of Z. 
so just manipulating the algebra. It 
turns out to be 1/2, 1 plus or minus 
square root of 1 minus 4z. 
has to be minus, out of the 2 choices for 
it to come out right for, and equal 0. 
and then, 1 minus 4z, that's 1 minus 4z 
to the half power. 
So we can use the binomial theorem, or 
the generalized version of the binomial 
theorem, due to Newton to express that as 
1/2 choose N, a generalized binomial 
coefficient, minus 4Z to the N, sum, 
summed over all N. 
So that's direct from the, generalized 
binomial theorem. 
now, there, on the left hand side, our 
coefficient is t to the n. 
On the right hand side, 
Well, we have to make a variable change 
to n to n plus 1. 
but setting coefficients equal, now we 
have this explicit expression for t sub n 
minus 1/2. 
1/2 choose N plus 1 minus 4 to the n plus 
1. 
That's the an explicit expression for the 
number of binary trees with N nodes. 
Now we can simplify that using the 
definition of the generalized binomial 
coefficient so, on the bottom you have 
the n+1 factorial and on the top, you 
subtract, 1, 2, up to n+1 from the 1/2 
and so we get this expression here, which 
looks a little bit, unwieldly, but You 
know, it's not, not too difficult. 
the next thing we can do is, out of the 
minus 4 to the N plus 1, you take minus 2 
to the N, and put them into those 
factors, and you get the odd numbers. 
and then there's a 2 to the n left over. 
and another one goes to cancel out the 
1/2. 
so you can check that. 
That's, just, arithmetic. 
and now, we're getting close to a, pretty 
simple, expression. 
because what you can do is write the 2 to 
the n as 2 over 1, 4 over 2, 6 over 3, 
and like that. 
and now, on the top, we're going to have 
2N factorial. 
On the bottom, we're going to have 
another, N factorial factor. 
and that gets us down to an explicit 
solution, T sub N equal 1/N plus 1, 2N 
choose N. 
These are famous numbers known as the 
Catalan numbers. 
This solution's been known for a few 
centuries. 
That's the third step in classic analysis 
of algorithms. 
So now, our question was, how many bits 
do we need to represent a binary tree 
with n internal nodes? And our answer is, 
you need a least log of the Catalan 
numbers' 
bits. 
but that's not quite a satisfactory 
answer. 
if you've got a program that's trying to 
figure out how to do it for a 1,000 nodes 
you've got to figure out how to calculate 
the number of bits from that expression 
or it's for a million nodes. 
it's not so clear maybe need some 
expertise in numerical analysis. 
and when you think about this sort of 
problem people today think, well, once I 
have a mathematical expression. 
I can just, call a math package, and, and 
get the answer. 
And that's, maybe, sort of the case of 
having a computer or calculator do it. 
But think back to the classical, 
mathematicians in the 18th and 19th, 
17th, 18th, and 19th centuries. 
They did all these calculations by hand, 
and so they're looking for, really 
efficient ways to, calculate things, not 
using a computer at all. 
And in fact, what's called asymptotics, 
or asymptotic estimates, has been really 
a, played a central role in scientific 
calculations for, for centuries. 
and so, there's a, a vast array of 
techniques available to us to so a little 
bit better job than giving a complex 
mathematical expression. 
and perhaps the most famous example of 
that is Stirling's approximation, 
developed in the 18th century. 
And it says that log of N factorial, is 
about N log N - N + log square root of 2 
pi N. 
And actually that squared of 2 pi, was 
not known, for, quite awhile. 
That was Stirling's, contribution. 
and it's a very accurate approximation 
and a lot easier to compute than log of N 
factorial. 
even for 100, so this table just gives 
what the, 460 is N log N, the 360.52 is 
what you get when you subtract N, 363.74 
is what you get when add N log, the 
square root of 2 pi N. 
So it's very close even for 100. 
And for large It remains, very close. 
For a thousand, it's accurate to within 
2, and for 10,000, it's still very close. 
Extremely, accurate, approximation, to ln 
n. 
and the rationale for using 
approximations of this sort is that we 
can get very precise numbers which is 
really what the scientist wants for 
specific values. 
not only that, we get, using just a few 
standard functions, we get concise 
representations of the functions that, 
that we care about that are in a 
canonical form that, that we can work 
with. 
and not only that by adding more terms, 
we can have what's called asymptotic 
expansions, where we can get the accuracy 
we want. 
just by adding more terms. 
In all the methods that we consider have 
that property and this was developed over 
and used and successfully over many years 
by many scientists and mathematicians. 
Just mentioned a few Euler and Poincare 
and Bruijn just from different centuries 
but there's many many others. 
that, have developed and work with, 
asymptotic expansions and they play a key 
role in the analysis of algorithms. 
For example, for our problem, we have 
this solution, 
1/N + 1, 2N choose, N. 
and actually, to put it in a convenient 
form for applying Stirling's 
approximation, we just write that as e to 
the log of it, and so the log of 2n 
choose n, is log of 2n factorial -2 log 
of n factorial, and then there's a -log 
of n + 1, for the 1 over n + 1. 
And now we can apply Stirling's 
approximation to the first two terms. 
in the second term is very close to log 
in, of course. 
so just substituting that in, we get a a 
long expression. 
log of 2n factorial just using Sterling's 
approximation is about 2n, log 2n minus 
2n and plus log squared of 4n. 
and then the next 2 log n factorial, 
that's the next term 2 n log N minus n 
plus log squared to pan, and then there's 
a minus log N. 
And now it's just a little bit of algebra 
just to practice your algebraic ability 
just to check that this is true. 
So log of square root 4 pi n minus 2 log 
of square root of 2 pi n equals minus log 
of square root of pi n. 
so with a pencil and paper, you can 
figure that out. 
and then the 2 log 2N most of it cancels 
and all that's left is 2N log 2 minus the 
square root of log pi N minus the log N. 
And then if we undo the exp-log we get 
that asymptotic estimate for the number 
of binary trees with n nodes. 
And that's a very accurate asymptotic 
estimate, it's very close to, very, very 
close to 1/N plus 1 2N choose N. 
But it's much more useful. 
we can, and if we want more accuracy we 
could get it. 
but that's in, in a standard form and 
even by hand you can compute values or if 
you want to answer our question, how many 
bits do you need for binary tree of 
internal nodes? you can answer it 
directly, it's about 2N minus 1.5 log 
base 2 of N. 
And even a working programmer is going to 
say, oh that's a little less than 2,000 
bits for N equals 1,000. 
And by the way, it's actually easy to 
represent a binary tree with 2 end bits. 
You just do a preordered traversal, an 
output of 0 when you hit an internal node 
and a 1 when you hit an external node. 
So that kind of answer is very satisfying 
to programmers, you can do it with a 
little less than 2 N bits, you can do it 
2N bits and the best you could possibly 
do is a little less than 2N bits and 
that's the kind of answer that, that we 
want to see. 
So that's a very classic application of 
analysis of algorithms. 
And particularly, in the 60s' and 70s' 
and even 80s' there were a wide, wide 
variety of problems that needed to be 
studied in this way. 
So, so, that's the basic summary. 
Develop a recurrence relation. 
Derive an equation of the generating 
function. 
Extract the coefficients. 
Do an asymptotic approximation. 
classic techniques in analysis of 
algorithms. 
And so when Philippe and I started our 
careers we had learned this, we knew the 
math and well we learned more math and 
are able to do this and able to attack 
many, many problems. 
but our challenge was that we had to face 
the idea of teaching this stuff to 
computer science students and 
particularly as the years started to wear 
on we got into maybe 1980, the students 
had lots of computer science but not so 
much math. 
So a, a challenge that, that we faced 
just in furthering our, our, being 
successful as teachers and researchers is 
how we're going to efficiently teach this 
stuff to CS students. 
This is a type of thing that anybody who 
wants to use a computer effectively 
really needs to know how we're going to 
teach it To CS students, so that's the 
first major theme in the story. 
we knew the math, we knew how to analyse 
the algorithm, how we're going to teach 
other people to do it.