Today we're going to talk about 
asymptotics. 
this is mathematics that was developed 
well, well before the advent of 
computers. 
in the 18th and 19th centuries. 
but it's quite relevant to the analysis 
of algorithms and to analytic 
combinatorics. 
we'll start of by talking about the 
standard asymptotics scale. 
So the goal is to develop concise and 
accurate expressions that give us good 
estimates of the quantities we're 
interested in studying. 
as I mentioned in the first. 
The lectures the big-oh notation is 
really not adequate for this if you say 
big-oh of log N, it doesn't give you an 
accurate measure of the, of the quantity 
it's on upper bound and it's within a 
constant factor and there's no way to get 
a precise estimate of of what the 
quantity is. 
if we had take a definition like this say 
H of N for the harmonic numbers that 
one's accurate but it's not concise take, 
it's going to take time to compute. 
the exact value that you want. 
Now that, that's not too bad but still 
the spirit of what we're talking about is 
to try to get accurate and concise 
expressions like this one. 
natural log N plus gamma plus big-oh of 
one over N so that one for large values 
of N. 
will give, a numerical result that's, 
very close to the, quantity that we're 
interested in studying. 
And we'll see lots and lots of examples. 
But that the, basic goal. 
we want concise and accurate estimates of 
the quantities, we're interested in 
studying. 
Now, we won't go, crazy with defining 
what concise means. 
what, what I mean by it is, I've got 
standard functions, and I've got 
constants that are maybe known. 
and I want to be able to compute this 
value for large N. 
it's as simple as that. 
And I want to write a program we use a 
calculator to compute the value. And 
actually that, that kind of definition 
it's easy to understand the motivation 
for a scientist in the 18th and 19th 
centuries who were learning more about 
mathematical models the world, in coming 
up with functions that describe what 
there, what ever they're interested in 
studying. But they wanted to be able to 
do calculations, in order to be able to 
compare their hypothesis with what goes 
on in the mathematic, in the natural 
world. And without asymptotics it would 
be hard to do so because without 
computers you definitely need to be able 
to compute your answer. 
And that's always a good perspective to 
have in the back of our minds when we're 
thinking about asymptotics. 
so, this is just, reminder, I talked 
about these notations, earlier on, so, 
the big, bigger notation for upper bands, 
if you say G of N equals bigger graph of 
N. 
That means absolute value of a ratio is 
bounded from above as N goes to infinity. 
and we are going to use that notation, 
for error terms but not for, our, our 
leading terms. 
also we use, a little-oh notation which 
says that 
G of N, is little-oh of F of N, if the 
ratio tends to zeros and approachs 
infinity so that's GN's asymptotically 
smaller than F of N. 
And again, we use that for error terms, 
in fact, often we use this, so called 
Pildon notation, which just says, that G 
of N and F of N ratio approachs one as N 
approachs infinity, that's the weakest 
non trivial little-oh. 
so 
We use those notations to come up with, 
approximations, 
So, if we say that G of N equals F of N 
plus big-oh of H of N. 
It means the error will be within, at 
most, a constant factor. 
Of H of N, as N increases. 
A little-oh means that we know the error 
will decrease as N increases. 
And that's good. 
That, means that for larger N we get a 
better result. 
Intelda again, is the weakest non trivial 
little-oh .. 
As N increases we expect a better result. 
And that's, the, basic, approximations 
that we're going to be trying to develop. 
so now with that background, what we're 
looking at is 
Developing a series of functions, and if 
we have a series of functions Gk with Gk 
plus one equal little o of Gk so that's a 
decreasing an asymptotically decreasing 
series of functions, then if we write. 
Fn as the linear combination of those as 
they decrease. 
We call that an asymptotic expansion of 
the function f. 
And since the functions decrease the 
expansion is supposed to get more 
accurate as we add more and more terms. 
Precisely, it represents the collection 
of formula f of n is big-oh of G sub 
zero. 
It's also C0 G0 plus big-oh of G sub one 
and, and so forth. 
And we can pick off of this list of 
formulas. 
the one that suits are purposes best, in 
terms of, getting, an accurate estimate 
of the quantity we're looking at, and 
this will become more clear, when we look 
at specific examples. 
so we're using big-oh notation, but in 
the specific technical sense we want to 
be able to be insured that we can get 
more accurate asymptotic estimates, if 
needed. 
so the standard scale we use the 
functions gk we use. 
Powers of n and logn and maybe logn and 
Log, Log N N exponentials. 
so those are the st, standard functions 
that we want to use. 
And we'll see it's very easy to express 
many of the functions that arise in 
scientific studies in terms of the 
standard scale. 
and we'll give it, it's not necessary to 
give a detailed definition of this. 
So typically, what happens is, we only 
use a few terms, maybe two, three or four 
terms, a second, or third or fourth 
equation from this. 
when the unused terms are extremely 
small, that's when we stop. 
because we have the big-oh estimate that 
says, we're within, a constant of that 
unused term, and it's extremely small, 
relatively. 
That's when we stopped. 
[COUGH]. 
So we use the tilda notation if we don't 
want to bother carrying around the big-oh 
information. 
And a lot of times, that simplifies the 
calculations, and there's no reason not 
to. 
We usually check our asymptotic estimates 
against, the actual values, to make sure, 
that what we have is giving us the 
accuracy that we want. 
And if we do mathematically want to 
specify information on the unused terms, 
we go ahead and do that using the big-oh 
notation or the little O notation. 
But the main point is that the methods we 
use in principle should extend to any 
desired precision. 
if we need more terms we can get them. 
And that's a very big difference from the 
use of the big-oh notation. 
in the theory of algorithms where it's 
both expressing an upper bound and 
capturing the concept of the worst case. 
This is more in the spirit of of, of 
science in the origins are clear in the 
eighteenth and 19th centuries where 
people wanted to be able to calculate 
things and then compare those with the 
results of scientific experiments. 
And that's what we want to do in the 
analysis of algorithms. 
and that's why. 
we embrace all of this classical 
mathematics. 
so here's an example from that w, we 
looked at in the second lecture. 
so there's 
We came up against a theorem that was 
going to give us coefficient abstraction 
for. 
This was for solving linear recurrences. 
and eventually we found through the use 
of generating functions that the quantity 
that we're interested in is the 
coefficient of z to the n in the ratio of 
two polynomials. 
and so what we. 
Can do with asymptotics is take a pretty 
complicated theorem statement. 
that I'll show in just a second. 
And reduce it down to actually a pretty 
general result. 
The coefficient of z to the n in the two, 
ratio of the two polynomials is 
asymptotic to a constant times beta bn, n 
to the [INAUDIBLE] minus one. 
Where beta is the smallest modulis root 
of that 
Polynomial in, in the dom, denominator in 
new is its multiplicity. 
So this is just picking the leading term 
offer the more detailed theorem. 
so in lecture two I gave this detail 
theorem that show that the coefficient of 
Z to the N in that ratio there's a term 
called corresponding to each zero of G of 
Z. 
and then according to its multiplicity. 
And the, with [INAUDIBLE] can we can not 
worry about 
All the smaller terms in that sum, and 
just pick out the large, largest one in a 
precise, technical sense. 
so for example if the roots are three and 
two then it might be three to the n and 
three to the n plus two to the n. 
Then you can see as n gets even to eleven 
they're pretty close. 
and when n gets very high, they're going 
to get closer and closer. 
so usually, the, the pole of smallest 
modulus really dominates. 
so no. 
Question three to the N plus two to the N 
is asymptotic to three to the N. 
You can forget about the two to the N for 
large N. 
and [COUGH]. 
in fact the convergence is exponentially 
fast as N gets large even by one the, it, 
it gets closer and closer to being 
accurate. 
the ratio gets closer and closer to one. 
So usually that, that poll of smallest 
modalist, the the place where the 
denominator goes zero closest to the 
origin, that's the one that really 
matters. 
And I emphasize this because this 
particular scenario turns to be very 
important in a general context. 
Later on, in analytic combinatorics. 
Now there are situations, depending on 
what these polynomials are, where the 
poles are close together. 
or, the multiple poles very close to the 
one of smaller modulus. 
And so in those kinds of cases, we have 
to figure out how to extract, the leading 
terms. 
But still, it's very important to realize 
that we don't need to carry around, the 
small ones. 
So, sure. 
If it, if one of the roots is, two, and 
the other one is one half. 
And the other is one over 1.999. 
And nine. 
it's not going to be that close. 
You'd be off by a factor of two if you 
try to throw that one away. 
but it's easy to figure that out, and 
it's important to know that it's easy to 
throw away the small ones. 
so here's how analysis would go for a 
recurrence, say like one of the earlier 
recurrences that we started out with. 
A sub N equals five. 
An minus one minus six, AN minus two. 
And A zero equals zero and A one equals 
one. 
So 
Not to 
We only worry about the 
The. 
[COUGH] Root of G that's smallest. 
so to solve the recurrence we make it 
valid for all N then we multiply by Z and 
sum on N to get a polynomial and that 
gives us for the generating function a 
ratio of two polynomials. 
And what we're interested in is the 
coefficient of Z to the N in that 
generating function. 
And now we can just plug and chug in the 
theorem. 
smallest root of the denominator is one 
third, so it's going to be asymptotic to 
three to the N and then we. 
Go ahead and calculate the constant. 
And if you plug in the values for the 
constant in that formula you just get 
one. 
And if you want to apply the same thing 
to say, the recurrence for the Fibonacci 
numbers. 
Again, the same steps are going to work. 
In that case, the constant will be 
1/sqrt(5), and it will be phi^n, the 
golden ratio to the n. 
The extra term in that case is phi hat, 
which is less than one and totally 
negligible. 
So with acentonics we get a relatively 
simple, general theorem that gives us a 
precise and concise result for a big 
family of problems. 
okay, so back to the basics, where do we 
start out, where do we get the asymptotic 
expansions, that we need to start out. 
Well for a lot of the generating 
functions that arise, Taylors thorem 
immediately, gives us an answer, it's, 
expansion through power series and 
Taylors thorem they're infinite, but, 
since they converge, you, it can stop at 
any point, to give results like this. 
In principal we can take as many turns as 
we want off the, infinite series, and 
then. 
We have [COUGH] a asymptotic series in 
the standard scale. 
So again, these are just immediate from 
Taylor's Theorem, where the term of Xn/n! 
of N, Is the nth derivative of the 
function. 
So we looked at all of these when we 
talked about expanding generating 
functions. 
The difference now is with asymptotics, 
we're only interested in taking a couple 
of terms for the purpose of being able to 
accurately compute values. 
So those are standard examples. 
Now these are Taylor's Theorem just for X 
goes to zero. 
Actually we're usually interested in 
coefficient Z to the N as in increases, 
so what we'll do is just substitute one 
over n in all of these formulas to get 
asymptotic expansions and these are maybe 
in more familiar terms, if you wanted to 
compute e to the one over N, say for N 
equals 1,000,000 this will tell you it's 
going to be pretty close to one. 
That'll be one plus one over a million 
plus one over two times a million 
squared. 
that kind of be worth trying to compute 
that any more accurately than that. 
this will give the very great accuracy 
just with a few terms. 
same log of one over one plus one over N 
for N, N equals a million. 
That's pretty close to one millionth the 
next term you will notice until twelve 
decimal places out and the next one 
eighteen decimal places out. 
If you just wanted to a few decimal 
places. 
use one over a million. 
That's the whole idea of asymptotics. and 
a binomial has this is for K constant 
we'll have a similar kind of character. 
now this gets more complicated if K grows 
with N and that's, be one of the things 
that we'll talk about later on. 
the one that we use really most often is 
a geometric so anyway that's the what you 
get when you plug in one over N in the 
straight geometric series. 
One over N minus, what it says is one 
over N minus one is really close to one 
over N for a million. 
again next term out wouldn't happen for 
twelve decimal places. 
so those are basic building blocks of the 
asymptotics expansions that we work with. 
so just as exercises just using those 
simple formulas then we can get 
relatively accurate approximations of 
say, sums and differences of functions. 
just using those formulas. 
And so it's worthwhile to take a look at 
these exercises, and not just as getting, 
getting started a problem in asymptotics. 
we specify the function and then we 
specify how accurately we want to 
estimate it. 
and so 
so these two problems, it's definitely 
worthwhile just working for a second on 
those. 
And if you go ahead and just, plug in 
from the formula, from before, the 
previous slide. 
log of one plus one over N is one over N 
minus one over 2N2 squared plus one 
big-oh of one over N3. 
cube. 
N log of N minus one over N is minus one 
over N, 
and so the one over N terms cancel. 
and then you have two, one over two N 
squared terms which makes it just minus 
one over N squared plus big-oh, one over 
N cubed. 
So right away you can see the log of one 
plus one over N is a rather complicated 
function but we can approximate it very 
accurately as just minus one over N 
squared and that's going to be quite 
accurate for in in the practical ranges 
of interest. 
If it's minus than what happen is the one 
over N squared terms cancel out we're 
just left with two over N. 
so that's just a simple, simple example 
of asymptotic expansions using the basic 
information that we get from Taylor's 
theorem. 
[COUGH] and then combining those results 
really just using algebra. 
and for lots and lots of functions that 
come up we can apply techniques like this 
to develop accurate expansions. 
that's what we'll look at next.