okay, next we'll tak a look at the basic 
techniques that we use for manipulating 
asymptotic expantions, to derive, 
accurating and concise, estimates of the 
quantities that we're trying to study. 
So are goal is to develop an expansion on 
the standard scale for, I or any 
expression that might arise in the 
analysis and these are just examples of 
the kinds of expressions that, might show 
up, some are artificial but some of them, 
actually turn up in are, analysis, so we 
saw two and she's in, 
Studying the catalan numbers, and the 
problem with some of these, like, 2N 
choose N, it might be hard to compute 
that, so, imagine a, seventeenth century 
mathematician, tryin to compute that for 
N equals a thousand that's a lot of 
multiplications, or imagining, imagine a 
computer programmmer today given the job 
of computing that, it's simple to define, 
but if you use the basic definition, for 
N equals a million, a million factorial's 
a pretty big number, so you have to deal 
with. 
Some way. 
On the other hand, using asymptotic 
expressions, we're going o get all of 
these in the kind of coherent form, where 
we can be confident that we can work with 
them. 
so there's lot of different techniques 
that we use and each one of them is 
relatively simple but still it's 
worthwhile calling out example of each. 
So, I may look at each one of these 
simplification, substitution, factoring, 
multiplication, division and composition, 
and, they Seem not really simple to call 
out, but on the other hand, when faced 
with dealing with one of these functions, 
you really want to think in terms of, 
there is an easy way to do this. 
one of these basic ways, just have to 
figure out which one it is. 
and there's also the X Log trick is an 
important one, or technique, and I'll 
show that in a minute. 
so again the whole idea is that a lot of 
times we have, not just these quantities, 
but maybe they combine in some way. 
so. 
Like what's the value of one over four to 
the n 2n choose n. 
that's an expression that arises that's 
of importance in the analysis of 
algorithms. 
and if he has to program and try to 
compute that for an stand over sixth its 
going to be a challenge. 
it'll actually see that its relatively 
simple to express these in terms of 
standard functions of the asymptotics and 
of these functions and all of the 
functions that arise are we can, we can 
do that. 
so lets take a look at. 
The various techniques. 
So the first thing is that. 
An asymptotic series is only as good as 
its big O term, so that means there's no 
point in carrying around smaller terms, 
if you have something that's encompassed 
by the big O just drop it, it's only 
going to make the calculation more 
complicated and it's not helpful in any 
way, so we don't write log N plus gamma 
plus O of one, where gamma's a constant 
becasue the O of 1 says the errors 
bounded by some constant and so that 
constant might as well gamma or, or 
whatever it's 
better to say that, write down this 
expression as log N plus O of 1, 
it's more compact. 
so [COUGH] 
The other idea we already talked about 
was substitution, where you can just 
change variables in a known expansion. 
So the Taylor series for log of one plus 
x u, is x minus x squared of two plus x 
squared of three, and so forth. 
and if we just plug in a different value 
for x, when wee plug in 1 / N then we get 
the expansion. 
so that's one that technique that we 
already used. 
factoring. 
A very common thing to do is to estimate 
what the leading term is. 
Then factor that out, and expand the 
rest. 
So, look at this function. 
One over n^22+n. 
+ n. 
And we'd think to ourselves. 
What's, what's this going to be, close 
to, when n is large? 
Like, n is a million. 
It's going to be close to one over n^2.2. 
So we might as well factor out the one 
over n^2.2. 
And then, in this case, what we're left 
with is 1 / 1 + 1 / n and that's a 
geometric series. 
And we have asymptomatic expansion for 
geometric series. 
So expand it, since it's 1 + 1 / n. 
It's 1 - 1 / n, + 1 / n^2. 
so and we could take that to more terms 
if we wanted to but that's an 
asymptomatic expansion of that. 
If we use that expansion it, it says that 
for n equals 1,000,000. 
That value's going to be very close to 
one over n squared. 
the relative area be, error that we would 
make would be one over n. 
And that, one over 1,000,000 in that 
case, which is probably small enough for 
our purposes. 
you'd distribute that so it's one over N 
squared - 1 / n^3 + big O of 1 / n to the 
4th. 
That's a asymptotic series in the 
standard scale for one over N squared 
plus N. 
very easy to obtain. 
multiplication. 
So multiplication is just algebra and but 
also employing simplification when we 
have smaller terms, we throw them out. 
So, let's look at the square of the 
harmonic numbers so we did an estimate of 
the harmonic numbers, we talked about the 
asymptypes series for the harmonic 
numbers, it's given by proximation with a 
sum and I talked breifly about that and 
we'll talk more about, about that kind of 
asymptotics later. 
So the harmonic number is approximated 
by, log N plus gamma plus big O of one 
over N, where gamma is, or looks constant 
in point.577. 
So to compute the square of the harmonic 
numbers we have. 
The square though. 
So that's two terms with 
three two factors with three terms each 
so we're going to wind up with six 
factors when we add all that together. 
So log N times each one of those, log N 
squared plus gamma log N, plus big O of 
log N over N. 
inside big O we usually don't specify the 
base of the logarithm since it only 
differs by a constant so it doesn't 
matter that it's natural log, so we just 
write log this means it's not specified 
at some constant. 
Then the next row is gamma times each 
one. 
Gamma*log(n) plus gamma^2 plus O(1/n). 
And the next term is O(1/n) times all of 
them, O(1/n)*log(n). 
Over n. 
Gamma*O(1/n) is O(1/n), and O(1/n)*O(1/n) 
is O(1/n^2). 
So that gives us nine terms, but we can 
throw a lot of them out. 
because well first of all, all the big O 
terms you just picked the largest one. 
so big O of one over N squared is much 
smaller than log N over N so it can be 
subsumed in that, same with O of one over 
N. 
So all the big O terms and and there's 
four, five of them, get subsumed in that 
O of log N over N. 
there's the gamma squared and then gamma 
log N appears twice so that's in 
asymptotic series in the standard scale 
for the square of the harmonic members. 
Now just taking a look at this series 
it's important to note that. 
there's a un. 
a difference between the first couple of 
terms and the big O that we lost. 
So, log N squared. 
so n is a, a million [COUGH] log n that's 
going to be, some small integer, 
So log n^22 and 2 of log n is not, 
they're not that far apart. 
so it seems like we're going to need 
those. 
and then gamma^2 is a constant. 
But log n's a small integer. 
it's only a slight improvement in 
precision to carry on those terms. 
And so we're probably going to want those 
terms but when we get a divided by n, 
that's when we have a huge improvement in 
precision. 
Now, you can't always tell ahead of time, 
how far you have to go, to get this big 
improvement. 
But in real problems, it usually happens 
after three or four terms. 
and it's, and that's what happened here. 
If you look at a tables of these 
quantities for n100 = 100 
sorry a 1000, 10,000, and a 100,000 you 
can see, so h n squared is the quantity 
that we're trying to estimate and then, 
if you just tried to estimate it with log 
n squared, you can see you'ld still be 
off by a fair amount 10% for even a 
100,000. 
if you add the two gamma log in you come 
much closer and add the gamma squared 
actually were accurate to three decimal 
places because the next term the one that 
we're missing is going to differ. 
it's going to be bounded by a constant 
times log n over n n for 100,000. 
that's going to be out in the fourth or. 
The decimal place, assuming the 
constant's small which normally we assume 
it is asymptotic series because they are 
but we can check as in this case that 
that's an accurate approximation. 
So usually we'll try to carry it out long 
enough until we get this big improvement 
in precision. 
Alright, division. 
that's like multiplication. 
so 
let's look at this example hn = natural 
log. 
hn over natural log of n1. 
+ 1 so what we'll do for that is we'll 
expand the numerator and the denominator 
both. 
and then we'll use the geometric series 
to expand the denominator. 
And that'll give us a multiplication 
problem. 
So let's look at how that works. 
so [COUGH] h of n is 
log n plus gamma + O / 1 / N. 
That's the approximation that we've been 
using for H of N. 
Natural log of N plus + factor out a log 
N, and it becomes natural log of N plus 
natural log of 1 + 1 / N. 
Natural log of 1 + 1 / N is big O of 1 / 
N 
just from Taylor. 
So now we have the ratio of 2 
asymptomatic series. 
And, what we'll do is factor out the log 
end as before, so 
so let's divide both numerator and 
denominator by log n and so the numerator 
becomes 1 + gamma over log n + of 1 / n 
it's over 1 / n log n so we're 
simplifying that and then 
the denominator comes 1 + of 1 / N. 
We could make it one of 1 over log N. 
We're making it a little bit bigger. 
and, and again, that's just to simplify 
the formulas. 
If we did not get a sufficiently accurate 
estimate we could go back and try to 
correct that. 
But now 1 + O of 1 / N, if you expand as 
a geometric series, it just becomes one 
plus, one over one plus O of one over N 
is one plus O of one over N just as a 
geometric series. 
And again, if there are more terms, you 
could carry more terms out there. 
so now we have a multiplication problem, 
and if we mul, multiply that out, that's, 
a proof that the asymptotic expansion of 
HN over log of N plus one, to within of, 
one over N, is one plus gamma over log N, 
plus O of one over N, and again there's a 
big improvement, in precision when we get 
to the one over N term, so this is going 
to be a very accurate estimate of, that, 
more complicated quantity, as N 
increases. 
composition, so this is similar so we're, 
we're just going to substitute an 
expansion and figure out what to do. 
So if you had to compute e to the h of n 
you plug in the expansion for h of n and 
see what you get what you get is e to the 
log n + gamma + O of 1 / n. 
E to the log n, that's n. 
E to the gamma is E to the gamma. 
That's a constant and then what's left is 
E to the big O of 1 / N. 
And then, that one, you, expand, with 
Taylor. 
Although it's a little, more work to 
actually prove that. 
But you can, from now on, use that lemma. 
e to o of one over n is one + zero of n 
over n. 
and then that'll, and you can expand it a 
couple of terms, if you need to. 
and, that gives the simplification that 
E to the H N is N E to the gamma two of N 
one over N or N E to the gamma plus O of 
one. 
And again n e to the gamma that grows 
with n. 
O of one is a constant. 
So there's a big change in precision so 
that's going to be a very accurate 
approximation for large n. 
each time that we do an asymptotic 
expansion we go down to where we can, 
usually we try to go where we can get a 
big improvement in precision like this. 
And gives us a, a simple expression in 
terms of familiar functions for this 
thing, where otherwise it's growth might 
not be so obvious to see. 
and again you can see for n equals a 
million this is accurate to within one. 
absolute one, which is a fine small 
relative error. 
okay. 
x-log trick so this is a way to bring us 
in a position where we can apply the 
composition in more complicated 
scenarios. 
And, all we'll do is write F of X as. 
e to the log of f of x. 
Then we can expand log of f of x. 
And we can expand e to, that series as we 
did before. 
and here's a fine example. 
One minus one over n to the n. 
and when you see a thing like that you, 
you have to think. 
How would you compute that for that large 
values of n? 
ask a programmer where to compute that 
for N equals 1,000,000 maybe not 
necessarily so easy to do. 
It's going to at least take time 
proportionally and, and there might be 
precision problems or as with factorial, 
there might be problems in needing to 
carry too many digits. 
well actually the way people compute 
things like that is use the X log trick 
so that is we write that as E to the log 
of 1 - 1 / N to the N. 
and so the log of 1 / -1 to the N. 
We can bring the N down. 
it is N times the log of 1 - 1 / N. 
so now if we expand log of 1 - 1 / N 
again, using the Taylor series, we get -1 
/ N plus O of 1 over N^2. 
And then do the algebra. 
That's e^-1-1)+O(1/n). 
+ O of 1 / N. 
And again, eO(1/n) to the O of 1 /O(1/n). 
N that's 1 + O / N so that's 1/e. 
It says that, that function, 1-(1/n)^n, 
is going to be very close to 1/e. 
And again, that's the big improvement in 
precision we always look for. 
And again, we can check that for 
n1,000,000. 
= 1,000,000. 
That's accurate to six decimal places. 
Because the O says that the error is 
going to be out there around the six 
decimal place. 
so again when we're trying to understand 
what the value of the quantity is if we 
know it's 1 / e which is this constant of 
367879. that's very precise and concise 
information as opposed to that exact 
expression which maybe it's hard to know 
what it is. 
and when we start combining these kinds 
of formulas which we do all the time 
we're going to want to work with the 
precise and concise expressions. 
so that's the X-log technique, and we 
actually use that one quite a bit. 
so thinking about these various 
techniques here's just a couple more 
examples 
that you might want to try doing to make 
sure that you understand the kinds of 
techniques that we're using. 
so log of N over N - two, 2 with N, 1 / 
N^2 and HN^2 what's that constant times 
the one over N term, because we only got 
it to log, log N over N. 
And that's just to illustrate that if 
desired we can go to more asymptotic 
accuracy. 
maybe we need to do that because we've 
got a function where we're multiplying 
that thing by N squared and so we need 
more accuracy. 
just for example. 
so for log N minus two what we do is 
factor out the N so that's the leading 
term. 
And then we have log of 1 - 2 / N and 
then just expand the rest. 
and so it's - 2 over N plus big of one 
over N squared [COUGH], so, that's the 
solution to that one, and this one is, 
just, carrying out the asymptotic 
approximations to one more term, which 
is, one over N squared term, and then 
that gives the coefficient of log N over 
N is one. 
and again these types of things with as 
with any kind of mathematics require 
little bit of practice but the, the 
techniques are, are so simple its not 
difficult to learn how it do these kinds 
of expansions. 
so that's a quick introduction to 
manipulating asymptotic expansions.