0:04

Okay, next we'll take a look at the basic techniques that we use for

Â manipulating asymptotic expansions to derive accurate and

Â concise estimates of the quantities that we're trying to study.

Â So our goal is to develop an expansion on a standard scale for

Â any expression that might arise in the analysis.

Â And these are just examples of the kinds of expressions that might show up.

Â Some of them are artificial, but some of them actually turn up in our analysis.

Â So we saw 2 inches, and we studied the catalan numbers.

Â And the problem with some of these, like 2 inches N,

Â it might be hard to compute that.

Â 0:46

So imagine a 17th century mathematician

Â trying to compute that for n=1,000, that's a lot of multiplications.

Â Or, imagine a computer programmer today given the job that computing has,

Â it's simple to define, but if you use the basic definition for n = a million,

Â a million factorials, pretty big number, so you have to deal with it in some way.

Â On the other hand, using asymptotic expansions,

Â we're going to get all of these in a kind of coherent form

Â where we can be confident that we can work with them.

Â So there's a lot different techniques that we use and each one of them is relatively

Â simple but it's still worthwhile calling out examples of each.

Â So, and we'll look at each one of these simplification,

Â substitution, factoring, multiplication, division, and composition.

Â 1:43

They seem 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'll also be a 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 1 over 4 to the N 2N, choose N.

Â That's an expression that arises that's of importance in the analysis of algorithms.

Â And if you ask the program to try to compute that for N equals 10 to the 6th,

Â it's going to be a challenge.

Â And we'll actually see that it's relatively simple to express this in terms

Â of standard functions via asymptotics.

Â And all of these functions and all of the functions that arise we can do that.

Â 2:50

So, let's take a look at the various techniques.

Â So the first thing is, that an asymptotic series is only as good as its O-term.

Â So that means there's no point in carrying around smaller terms,

Â if you have something that's encompassed by the 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 + gamma + O of 1 where gamma is a constant,

Â because the O of 1 says the air is bounded by some constant and

Â so to have that constant might as well be gamma or whatever.

Â It's better to say that write down this expression as log N + O of 1,

Â it's more compact.

Â So, 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 1 + X is X-X

Â squared over 2 + X squared of 3 and so forth.

Â And if we just plug in a value for X, we plug in 1 over n,

Â then we get the expansion, so that's one 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, 1/N squared plus N and we think to ourselves,

Â what's this going to be close to when N is large, like N is a million.

Â It's going to be close to 1/N squared, so

Â we might as well factor out the 1 over N squared.

Â And then in this case, what we're left with, is 1/1 + 1/N and

Â that's a geometric series and we have asymptotic expansion for geometric series.

Â So expand it since it's 1+1/N,

Â it's 1-1/N or 1/N squared.

Â So and we could take that to more terms if we wanted to but

Â that's an asymptotic expansion of that.

Â If we use that expansion is says that for

Â N=1 million that value is going to be very close to 1/N squared.

Â The relative error that we would make

Â would be 1 over 1,000,000 in that case which is small enough for our purposes.

Â 5:33

Multiplication, so multiplication is just algebra but

Â also employing simplification when we have smaller terms and we throw them out.

Â So let's look at the square of the harmonic numbers, so

Â we did estimate on the harmonic numbers.

Â We talked about the asymptotic series for the harmonic numbers

Â is given by approximation with the sum and I'll talk briefly about that.

Â And we'll talk more about that kind of asymptotics later.

Â So the harmonic number, is approximated by log N + gamma plus big O,

Â over 1 over N, where gamma is always constant 0.577.

Â So, to compute the square, of the harmonic numbers, we have to square those.

Â So, that's 2 terms with 2 factors with 3 terms each.

Â So we're going to wind up with six factors when we add all that together.

Â So ln N times each one of those,

Â ln N squared + gamma ln N + big O (ln 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.

Â 6:51

Then the next row is gamma times each one, gamma log N + gamma squared + O of 1/N.

Â And the next term is O(1 over N) times all of them, O(1 over N),

Â log N over N gamma times O(1 over N) is O(1 over N), and

Â so O(1 over N) times O(1 over N), so O(1 over N) squared.

Â 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 pick the largest one.

Â So, big O of 1 over N squared is much smaller than log N over N so

Â it can be [INAUDIBLE] in that.

Â Same with O of 1 over N, so all the big O terms and

Â there's five of them, get subsumed in that O of log n over n.

Â There's the gamma squared, and the gamma log N appears twice, so

Â that's an asymptotic series in the standard scale for

Â the square of the harmonic numbers.

Â Now just taking a look at this series,

Â it's important to note that there's a difference between

Â the first couple of terms and the big O that we lost.

Â So log N squared, so N is a million,

Â log N itâ€™s going to be some small integer so

Â log N squared and 2 log N is not there not that far apart.

Â So it seems like were going to need those and the gamma squared is a constant,

Â but log N is a small integer is only a slight improvement in precision to carry

Â on those terms and so probably want those terms.

Â But when we get a divided by N,

Â that's when we have a huge improvement in precision.

Â Now, we can't always tell ahead of time, how far you have to go before you get this

Â big improvement, but in real problems it usually happens after three or

Â four terms and that's what happened here.

Â If you look the tables of these quantities, for N equals 100, I'm sorry,

Â 1,000, 10,000 and 100,000, you can see,

Â so HN squared is the quantity that we're trying to estimate.

Â And then if you just try to estimate it with log N squared you can see it will

Â be off by fair amount 10% for even a 100,000.

Â If you add the 2 gamma log N you come much closer and add the gamma squared,

Â actually we're 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 and for

Â 100,000 that's going to be out in the fourth or

Â fifth decimal place, assuming the constant's small,

Â which normally we assume in these asymptotic series is 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.

Â 10:27

both and then we'll use the geometric series to expand the denominator and

Â that will give us a multiplication problem, so let's look how that works.

Â So [COUGH] H of n is log N + gamma + O of 1 over N,

Â that's the approximation that we've been using for H of N.

Â Natural log of N + 1, factor out a log N and

Â it becomes natural log of N + natural log of 1+1 over N,

Â natural log of 1 plus 1 over N plus big O 1 over N just from Taylor.

Â So, now we have the ratio of 2 asymptotic series,

Â and what we'll do is factor out the log N as before.

Â So, that's divide by numerator and denominator by log N and

Â so the numerator becomes 1 + N over log N, + 1 over N,

Â over 1 over N log N, so we're simplifying that,

Â the denominator becomes 1 + plus O over N.

Â We could make it 1 over N log N, to make it a little bit bigger 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.

Â And now 1 + O of 1 over N, if you expand as a geometric series,

Â it just becomes 1 + 1 over 1 + O of 1 over N,

Â is 1 + O of 1 over N, just as a geometric series.

Â And again, if there are more terms, you could carry more terms out there.

Â 12:14

So now we have a multiplication problem and if we multiply that out,

Â that's proof that the asymptotic expansion of HN over log

Â of N + 1 to with 1 over N is 1 + gamma over log N + O of 1.

Â And again, there's a big improvement in precision when we get

Â to the 1 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 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 the H of n and see what you get.

Â What you get is e to the log N + gamma + big O of 1 over 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 over N.

Â And then that one you expand with Taylor, although it's a little

Â 13:26

more work to actually prove that but you can from now on use that Lemma.

Â e to the O of 1 over N is 1 + O of 1 over N, and

Â you can expand it a couple of terms if you need to, and

Â that gives the simplification that e to the HN is Ne to the gamma

Â to then 1 over N or Ne to the gamma plus O of 1.

Â And again Ne to the gamma that grows with N over 1 as a constant so

Â there is a big change in precision, so

Â that's going to be a very accurate approximation for large N.

Â 14:31

And again, you can see, for N = a million, this is accurate to within 1,

Â absolute 1, which is a fine small irrelative error.

Â Okay, x blog log,

Â so this is a way to bring us into position where we can apply

Â the composition in more complicated scenarios.

Â And all we'll do is write f(x) as

Â e to the log of f(x), then we can expand the log of f(x), and

Â we can expand e to that series, as we did before.

Â And here's a fine example, 1- 1/N to the N and when you see a thing like that,

Â you have to think, how would you compute that for that log value of N.

Â Ask a programmer to compute that for N = a million,

Â maybe not necessarily so easy to do.

Â It's going to at least take time proportional to N, and

Â there might be precision problems or

Â as with factorial there might be problems in needing to carry too many digits.

Â 15:40

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 over N to the N-th.

Â So, in the log of 1- 1 over N to the N-th,

Â we can bring the N down, it's N times the log of 1- 1 over N.

Â And so now, if we expand log of 1- 1 over N, again,

Â using the Taylor Series, we have -1 over N, plus O of 1 over N squared.

Â And then do the algebra, that's e to the -1 + O(1/N) and

Â again, e to the O(1/N) = 1 + O(1/N), so that's 1 over e.

Â It says that that function,

Â 1- 1 over N to the N is going to be very close to 1 over e.

Â And again, that's the big improvement in precision we always look for and again,

Â we can check that for N = a million, that's accurate to six decimal places.

Â 16:43

Because the bigger 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 that it's 1 over e, which is this constant,

Â 0.367879, that's very precise and concise information, as opposed

Â to that exact expression which maybe is 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.

Â 17:24

So that's the exp 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- 2 to O 1 over N squared and Hn squared and what's that

Â constant, times the 1 over N term because we only got it to log n over N.

Â And that is just to illustrate that if

Â desired we can go to more asymptotic accuracy.

Â Maybe we need to do that because we have got a function where we are multiplying

Â that thing by N squared and so we need more accuracy, just for example.

Â 18:30

And so it's -2 over N plus big O of 1 over N squared, so

Â that's the solution to that one and this one is just

Â carrying out the asymptotic approximations to one more term which is

Â 1 over N squared term and then that gives the coefficient of log N over N is 1.

Â And again, these types of things,

Â as with any kind of mathematics, they require a little bit of practice.

Â But the techniques are so simple, it's not difficult

Â to learn how to do these kinds of expansions.

Â So that's a quick introduction to manipulating asymptotic expansions.

Â