Today, we're going to talk about asymptotics. This is mathematics that was developed 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 off by talking about the standard asymptotic 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 few lectures, the big O notation is really not adequate for this. If you say big O(log N), it doesn't give you an accurate measure of the quantity. It's an upper bound, and it's within a constant factor, and there's no way to get a precise estimate of what the quantity is. If we had to take a definition like this, say H sub N, for the harmonic numbers, that one's accurate, but it's not concise. It's going to take time to compute the exact value that you want. Now, that's not too bad, but still the spirit of we're talking about is to try to get accurate and concise expressions like this one. Natural log N + gamma + big O of 1 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's the basic goal. We want a concise and accurate estimates of the quantities we're interested in studying. Now we won't go crazy with defining what concise means, 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. I want to write a program or use a calculator to compute the value. And actually, that kind of definition, it's easy to understand the motivation for Scientists in the 18th and 19th centuries, who were learning more about mathematical models of the world and coming up with functions that describe whatever their interests in studying. They wanted to be able to do calculations in order to be able to compare their hypotheses with what goes on 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 a reminder I talked about this notation earlier on. So the big O notation for upper bounds. If you say g of N = big O of N. That means the absolute value of the ratio is bounded from above as N goes to infinity. And we're going to use that notation for error terms, but not for our leading terms. Also we use the little o notation which says that g of N is little o f(N). If their ratio tends to 0 as N approaches infinity. So that's gN asymptotically smaller than f(N). And again, we use that for error terms, in fact, often we use the so-called tilde notation, which just says that g(N) and f(N) ratio approaches 1 as N approaches infinity. That's the weakest nontrivial little o. So we use those notations to come up with approximations. So, if we say that g(N) = f(N) + big O(h(N)), it means the error will be within at most a constant factor of h(N) as N increases. A little o 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. And tilde again is the weakest, nontrivial little o. As N increases we expect a better result and that's 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 g k + 1 = little o(gk), so that's an asymptotically decreasing series of functions. Then if we write fN as a linear combination of those as they decrease, we call that an asymptotic expansion of the function f, and since the function's decreased, the expansion is supposed to get more accurate as we add more and more terms. Precisely, it represents the collection of formula, f(N) is big O of g sub 0. It's also c0, g0, plus big O of g sub 1, and so forth. And we can pick off of this list of formulas the one that suits our purposes best in terms 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 0 notation but then in the specific technical sense, we want to be able to be ensured 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 log N. And maybe log N and log log N in exponentials. So those are the 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 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, the second, third or fourth equation from this. When the unused terms are extremely small that's when we stop. Because we have the big O estimate that says we're within a constant of that unused term and it's extremely small relatively that's when we stop. [COUGH] So we use the tilde notation if we don't want to bother carrying around the big O 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 O 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 O 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 science, the origins are clear in the 18th and 19th centuries, where people wanted to be able to calculate things and then compare those with the results of scientific experiments. 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 that we looked at in the second lecture. We came up against a theorem that was going to give us coefficient abstraction 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 and the ratio of two polynomials. And so, what we can do with asymptotics is take 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 cb vn in the two ratio of the two polynomials is asymptotic to a constant times beta vn into the new minus 1 where beta is the smallest modulus root of the polynomial in the denominator and mu is its multiplicity. So this is just picking the leading term off of the more detailed theorem. So in lecture two, I gave this detailed theorem that showed that the coefficient of z to the n in that ratio, there's a term corresponding to each 0 of g of z. And then according to its multiplicity, and with asymptotics, we cannot worry about all the smaller terms in that sum and just pick out the largest one in a precise technical sense. So for example, if the roots are three and two then it may be 3 to the N and 3 to the N plus 2 to the N and you can see as N gets even to 11 they're pretty close, and when N gets very high they're going to get closer and closer. So, usually the pole of smallest modulus really dominates. So no question 3 to the N plus 2 to the N is asymptotic 3 to the N. You can forget about the 2 to the n for large N. And [COUGH] in fact the convergence is exponentially fast, as N gets large even by 1, it gets closer and closer to being accurate. The ratio gets closer and closer to 1. So usually that pull of smallest modulus that the place where the denominator goes 0, closest to the origin that's the one that really matters, and I've emphasized this because this particular scenario turns out to be very important in a general context later on in analytic combinatorics. Now there are situation depending on what these polynomials are where the polls are close together or the multiple polls very close to the one with small modulus. And 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 one of the routes is 2 and the other one is one-half, and the other one is 1 over 1.99999, it's not going to be that close should be off by a factor of 2. I'd try to throw that one away. But it seems 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 started out with. A sub N = 5 aN- 1- 6a- 2 when a0 and a1 = 1. So we only worry about the 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 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 in chug in the theorem. The smallest root of the denominator is one-third so it's going to be asymptotic to 3 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 one over square root of 5, and it'll be phi to the n, the golden ratio to the n. The extra term in that case is phi hat which is less than 1 and totally negligible. So, with asymptotics, we get a relatively simple general theorem that gives us a precise and concise result for a big family of problems. So back to the basics. Where do we start out? Where do we get the asymptotic expansions that we need to start out? For a lot of the generating functions that arise, Taylor's theorem immediately gives us an answer. It's an expansion through power series and Taylor's theorem. They're infinite but since they converge, they can stop at any point to give results like this. In principle, we can take as many terms as we want off the infinite series. And then [COUGH] we have a asymptotic series in the standard scale, so again, these are just immediate from Taylor's theorem where the term of x and n over n factorials the nth derivative of the function. So we looked at all of these when we talked about expanding generating functions and the difference now is with asymptotics we're only interested in taking couple of terms for the purpose of being able to accurately compute values. So those are standard examples. Now these are Taylor's theorem for x goes to 0 actually we're usually interested in coefficient zbn as n increases. So what we'll do is just substitute 1 over N in all of these formulas, to get asymptotic expansions. And these are in maybe more familiar terms, if you wanted to compute e to the 1 over N, say for N equals a million, this will tell you it's going to be pretty close to 1. It'll 1 plus 1 over 1 million plus 1 over 2 times a million squared. I'm not going to be worth trying to compute that any more accurately than that. This will give very great accuracy just with a few turns. Same log of 1 over 1+1 over N for if it equals a millionth, that's pretty close to 1 millionth. The next term you won't notice until 12 decimal places out, and the next one 18 decimal places out. If you just want it to a few decimal places, use 1 over a million, that's the whole idea of asymptotics. And binomial has, this is for k constant, will have a similar kind of character. Now, this gets more complicated if k grows within and that would be one of the things that we'll talk about later on. And the one that we used really most often, is geometric. So, anyway that's what you get when you plug in 1 over N, in the straight geometric series. 1 over N minus what it says is that 1 over N minus 1, is really close to 1 over N. For a million again next term out wouldn't happen for 12 decimal places. So those are the basic building blocks of the asymptotic 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 as just as getting started. A problem in asymptotics, we specify the function and then we specify how accurately we want to estimate it, and 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 before on our previous slide, log n 1 plus 1 over N is 1 over N minus 1 over 2N squared plus big O 1 over N cubed. And log of n 1 minus 1 over N is a minus 1 over N and so the 1 over N terms cancel, and then you've got 2, 1 over 2N squared terms, which makes it just -1 over N squared plus big O 1 over N cubed. So right away, you can see the log of 1+1 over N is a rather complicated function, but we can approximate it very accurately as just minus 1 over N squared and that's going to be quite accurate for N in the practical ranges of interest. If it's minus, then what happens is the 1 over N squared terms cancel out we're just left with 2 over N. So that's just simple, simple example of asymptotic expansions using the basic information that we get from Taylor's theorem. And then combining those results really just using algebra. 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.
