Next, we're going to take a look at 
techniques for dealing with coming up 
with asymptotic expansions when our 
quantities are expressed in terms of 
sums. 
and we, we'll see lots and lots of need 
for applying these techniques. 
A lot of times, our final result is in 
form, in the form of a sum and, so what 
we need to, in, in the, 
Maybe the terms at the end of the sum are 
much smaller than the terms at the 
beginning, so, we have to, use different 
techniques for different, 
different ranges of the sum. 
So here's a, an easy example called 
bounding the tail. 
So there's a famous problem where the end 
result is expressed in terms of this 
finite sum. 
N factorial, 
sm as K goes from zero to N minus one to 
the K over K factorial. 
So to deal with that one what we're going 
to do is write it as an infinite sum so 
the infinite sum K greater than equal to 
zero. 
Minus one to the K over K factorial, 
that's just one over E, E to the minus 
one. So that quantity that we're 
interested in is equal to, N factorial 
over E, minus this remainder term, and 
the remainder term is N factorial sum K 
bigger than N, minus one to the K over K, 
K factorial. So now what we can do is 
just see the this, infinite sum, we can 
bound it just absolutely it's, 
The first terms left someone over N plus 
one, the next ones left someone over N 
plus one squared, like that, which is 
just one over N. 
so that's a proof that, that infinite sum 
is just one over N, and that's just to 
proof that are original problem is N 
factorial over E to within big-oh of one 
over N, and again N factorial grows so 
fast that's an extremely accurate 
estimate of that sum, so that happens a 
lot the tail is very small. 
All and we can bound the whole tail at 
once. 
another, possibility is that, actually 
the, terms and the sum are rapidly 
increasing, in that case, it might be 
that, the only term that matters is the 
last one. 
For example, some of, K of K factorial. 
so if you just look at the last two terms 
of that sum, those are n factorial + n 
-one factorial, all the rest of them are 
all less than one over ten - one is n - 
one of them. 
To that gives it to within a big-oh of 
one over N. 
So, we have to have a feeling for, how 
the sum grows, where the big terms are, 
where the small terms are. 
But, often the sums arise the terms 
change in a way that we can take, the, we 
can find the most significant part of the 
answer and express that in and bound the 
rest of it to get our asymptotic 
expansion. 
the other thing that we do quite often is 
approximate with an integral and as I 
mentioned that's where our approximations 
for the harmonic numbers and the 
factorials or the stirling numbers come 
from. 
and we talked about those approximations 
and there's proofs of these simple things 
but we'll talk about better 
approximations u, later on. 
So, now those are three basic terms that 
we use for approximating finite sums but 
the main one is approximating with an 
integral. 
the [COUGH] classic formula for 
approximating sums within the goals is 
known as Euler-Maclaurin summation and 
there's two versions of that theorem 
given in the book and a bit of discussion 
about where it comes from most people are 
just going to be in the position of 
wanting to apply the theorem. 
So I have a finite sum. 
say K goes from one to N of F of K. 
that's this theorum gives an asymptotic 
series for that sum. 
kind of like a Taylor expansion that is 
expressed in terms of the derivitive of 
the function. 
there's a couple of unique things about 
the about the series when it comes to 
applying it. 
So one thing is that the error correction 
terms, what are they like? 
the first one is half f of n so that's at 
the end of the integral there's a little 
bit left out say. 
And then there's a constant that's 
dependent on the function. 
Sometimes we have explicit expression for 
this constant sometimes we don't. 
And actually the two cases we gave for 
harmonic numbers. 
We just name that thing gamma. 
We don't know how to express it in terms 
of other mathematical constants. 
For factorials, for Stirling 
Approximation of logn!), of N factorial 
it turns out that, that constant is 
square2*pi). 
root of 2 Pi. 
But that's something that has to be 
derived independently. 
And then the next error terms, the first 
one is the proportional to the first 
derivative of the function with 
coefficient 112 and then usually, we stop 
there because the next one is 
proportional to the third derivative 
with, constant of one over 720, so it's 
way smaller. 
Actually this series, like some other 
asymptotic series, doesn't neccesarily 
converge, the terms could start start to 
get bigger so we don't want to take to 
many, but we can know that. 
[COUGH] since it's an asymptotic series, 
if we stop with a big-oh O we can get an 
accurate result by stopping with just a 
few terms, and usually, for 
Euler–Maclaurin summation, we have the 
inner goal in just a few more terms so 
there's a lot of details about that in a 
book but in terms of applying it just 
using this form is very useful for a lot 
of applications. 
So classic example F of K equals one over 
K, integral of F of X DX for one to N is 
log N and then 
the Fn) of N is one over N, so that's a 
one over 2N. 
The constant is gamma, derivative is 
one2, over N squared for that's that. 
And then the next term, third derivative, 
is 14. 
over N fourth. 
So, that gives us the harmonic numbers 
for Euler–Maclaurin summation to within O 
N1/4. 
to the one fourth. 
So for N1,000,000, equals a million, 
you're not going to see a deviation from 
that for 24 decimal places. 
And the another classic example is 
Stirling approximation. 
and again now [COUGH] [COUGH] a log of N 
factorial 
that's the sum of K, so F of K is just K 
and so, 
sorry. 
F of k is log k. 
So its integral in computed out. 
and again, there's a big jump in 
precision right at the end where the last 
term's big-oh of one over N cubed. 
so that's going to be a very good, 
approximation, for, in the ranges of 
interest. 
and we can use that for, other functions 
as well. 
but these are the classics that arise 
again and again in the analysis of 
algorithms. 
And they're so useful because they're so 
accurate. 
so here's a very example of applying the 
information that was talked about so far 
in this lecture. 
so if we have Stirling's approximation 
just take it over and over N. 
now what we want to do is use that to 
figure out how 2N choose N rows. 
so we want to get two and choose N to 
within big-oh of one over N. 
so that's a straightforward exercise 
using the basic techniques that we've 
talked about with the algebraic 
manipulations on asymptotic series let's 
look at how it goes. 
and it's worth doing a couple of 
exercises of this nature and there are 
plenty in the book because the. 
number of terms that arise that appear 
daunting but you have the ability to wack 
them away with the big-oh and a lot of 
them cancel out. 
so lets look at this. 
So 2N choose N so that's 2N factorial 
over N factorial times N factorial so we 
have complicated terms multiplied 
together we're going to use the explode 
technique so that's equal to e to the log 
of 2n factorial minus two log N 
factorial. 
So change multiplication and division 
into sums of logs. 
okay so now those two functions we can 
apply Stirling's approximation. 
So the next line is just plugging in, on 
the first line is Durung's approximation 
for log of 2N factorial. 
That's 2N, that log of 2N, 
minus 2N plus log of square of four Pi N 
plus O of one over N. 
And the next line is subtracting off 
twice again the formula for Stirling's 
approximation minus two and log N minus 
plus log squared of two Pi N, not plus 
big-oh of one over N. 
So that's 
the that's the quantity so now we just 
have to do algebra. 
So in and you can see lot of things are 
going to cancel out so say the first term 
on the first line is 2n natural log of 2N 
The first term on the second line is 
minus 2N natural log N. 
So that first one is log 2N is log N plus 
log two or its going to be left there as 
2N Log two. 
then also look at the 
[COUGH] what happens to the terms 
involving square root of Pi? 
So, log a square root of four Pi N minus 
twice log square root of two Pi N. 
If you just multiply that out there's a 
log two minus two square root of log two 
the square root of then minus a log of 
square root of n so log two minus two log 
square root of two, that's zero, so all 
that's left is minus log square root of 
Pi N. 
so those two terms go to that one simpler 
term [COUGH] and the 2N log two and 
that's all that's left. 
The 2N cancels with minus two times minus 
N. 
and so now, that's 2N choose N equals E 
to the 2N log two minus natural log of 
square root of Pi N. 
Now, both of those terms have logs and 
it's E to that power. 
So now we can undo the X blog technique. 
the first term is four to the n. 
and the second term is, since it's minus 
one over square root of Pi N. 
So that's an asymptotic expansion for 2N 
choose N. 
two within one over N and again that's a 
big number but if we need it to compute 
2N choose N over four to the N then we 
get a function like one over square root 
of Pi N. 
and that's going to be what we going to 
want to estimate the quantity of that 
we're studying is as a typical example. 
So Stirling's approximation leads us to 
good approximations of binomial 
coefficients using the x log technique. 
so there we go one over four the n two 
inches in is one over square root Pi N. 
okay so here's a, here's an application 
in the real world of this kind of 
technique. 
so 
the question is for some kind of 
computational process the data might be 
represented as a binary tree with N 
internal nodes and the question is how do 
you represent that, that binary tree? 
and you can think about different ways to 
do it, but one thing that you can know is 
since there's one over N, the number of 
trees is the catalan numbers, you have to 
distinguish among all the trees, so you 
have to have at least log of that many 
bits in your representation. 
otherwise the number of things, the 
number of things that you can represent 
is less than two to the, that power and 
it's gotta be at least that big. 
if you use fewer bits, then you can't 
possibly represent all the trees. 
Now, someone who, didn't know esontotics, 
might respond, to the programmer, "That's 
how many bits you need." But how's the 
programmer going to compute that value 
for a million of a tree with a million 
nodes, it's, it's not concise, it's not a 
value that's, easy to compute and all 
this is a well known function, maybe, 
but, in general, faced with functions 
like that, that's not what we want. 
but using the calculation that we just 
did, you can say that there's an extra 
factor of N. 
[INAUDIBLE]. 
It's four to the N over square to pie N 
cubed. 
And if you take the log of that. 
log based two of that. 
that's two N minus 1.5 log N. 
That's really close to 2N. 
So need at least two N minus. 
So for 1,000,000 
[COUGH]. 
you'd need, you know? 
Two million - 1.5, natural log of, of log 
base two of a million, which is about 
twenty. 
so you need two million - 30 bits, at 
least. 
and that's an important. 
practical fact to know actually there's a 
way to represent binary trees with two n 
bits. 
So that's within 30 of the best that you 
can do. 
and so people who are working with a 
problem of this sort could stop there. 
I know at least 2,000,000 - 30 and I can 
do it with 2,000,000 and I'm going to be 
happy with that. 
in this is not the time to go through 
this in detail. 
but the method of representing binary 
tree into in bits is to just do a pre 
ordered traversal of the tree and write 
down zero every time you hit a internal 
node, and one when you hit a external 
node. 
and that's a unique representation of the 
tree that you can get back. 
if you look in Algorithms fourth edition 
there's a code for doing that 
representation. 
That's a F minus, fine example of why 
asintotics are useful. 
Takes the functions that we get from 
analysis and gives us a practical way to 
work with them. 
[COUGH] so that's an introduction to 
asymptotic on finite sums.