1 00:00:03,640 --> 00:00:09,036 okay, next we'll tak a look at the basic techniques that we use for manipulating 2 00:00:09,036 --> 00:00:14,501 asymptotic expantions, to derive, accurating and concise, estimates of the 3 00:00:14,501 --> 00:00:19,897 quantities that we're trying to study. So are goal is to develop an expansion on 4 00:00:19,897 --> 00:00:24,417 the standard scale for, I or any expression that might arise in the 5 00:00:24,417 --> 00:00:30,084 analysis and these are just examples of the kinds of expressions that, might show 6 00:00:30,084 --> 00:00:36,020 up, some are artificial but some of them, actually turn up in are, analysis, so we 7 00:00:36,020 --> 00:00:40,365 saw two and she's in, Studying the catalan numbers, and the 8 00:00:40,365 --> 00:00:45,475 problem with some of these, like, 2N choose N, it might be hard to compute 9 00:00:45,475 --> 00:00:51,607 that, so, imagine a, seventeenth century mathematician, tryin to compute that for 10 00:00:51,607 --> 00:00:56,922 N equals a thousand that's a lot of multiplications, or imagining, imagine a 11 00:00:56,922 --> 00:01:02,850 computer programmmer today given the job of computing that, it's simple to define, 12 00:01:02,850 --> 00:01:08,573 but if you use the basic definition, for N equals a million, a million factorial's 13 00:01:08,573 --> 00:01:11,640 a pretty big number, so you have to deal with. 14 00:01:11,640 --> 00:01:14,979 Some way. On the other hand, using asymptotic 15 00:01:14,979 --> 00:01:20,974 expressions, we're going o get all of these in the kind of coherent form, where 16 00:01:20,974 --> 00:01:24,541 we can be confident that we can work with them. 17 00:01:24,541 --> 00:01:30,461 so there's lot of different techniques that we use and each one of them is 18 00:01:30,461 --> 00:01:36,153 relatively simple but still it's worthwhile calling out example of each. 19 00:01:36,153 --> 00:01:41,693 So, I may look at each one of these simplification, substitution, factoring, 20 00:01:41,693 --> 00:01:47,822 multiplication, division and composition, and, they Seem not really simple to call 21 00:01:47,822 --> 00:01:53,946 out, but on the other hand, when faced with dealing with one of these functions, 22 00:01:53,946 --> 00:01:58,662 you really want to think in terms of, there is an easy way to do this. 23 00:01:58,662 --> 00:02:03,379 one of these basic ways, just have to figure out which one it is. 24 00:02:03,379 --> 00:02:08,869 and there's also the X Log trick is an important one, or technique, and I'll 25 00:02:08,869 --> 00:02:13,726 show that in a minute. so again the whole idea is that a lot of 26 00:02:13,726 --> 00:02:19,217 times we have, not just these quantities, but maybe they combine in some way. 27 00:02:19,217 --> 00:02:22,640 so. Like what's the value of one over four to 28 00:02:22,640 --> 00:02:27,307 the n 2n choose n. that's an expression that arises that's 29 00:02:27,307 --> 00:02:30,241 of importance in the analysis of algorithms. 30 00:02:30,241 --> 00:02:35,574 and if he has to program and try to compute that for an stand over sixth its 31 00:02:35,574 --> 00:02:39,975 going to be a challenge. it'll actually see that its relatively 32 00:02:39,975 --> 00:02:45,375 simple to express these in terms of standard functions of the asymptotics and 33 00:02:45,375 --> 00:02:50,243 of these functions and all of the functions that arise are we can, we can 34 00:02:50,243 --> 00:02:52,510 do that. so lets take a look at. 35 00:02:52,510 --> 00:02:56,510 The various techniques. So the first thing is that. 36 00:02:56,510 --> 00:03:01,862 An asymptotic series is only as good as its big O term, so that means there's no 37 00:03:01,862 --> 00:03:07,414 point in carrying around smaller terms, if you have something that's encompassed 38 00:03:07,414 --> 00:03:12,164 by the big O just drop it, it's only going to make the calculation more 39 00:03:12,164 --> 00:03:17,450 complicated and it's not helpful in any way, so we don't write log N plus gamma 40 00:03:17,450 --> 00:03:22,735 plus O of one, where gamma's a constant becasue the O of 1 says the errors 41 00:03:22,735 --> 00:03:28,605 bounded by some constant and so that constant might as well gamma or, or 42 00:03:28,605 --> 00:03:33,588 whatever it's better to say that, write down this 43 00:03:33,588 --> 00:03:37,200 expression as log N plus O of 1, it's more compact. 44 00:03:37,200 --> 00:03:43,388 so [COUGH] The other idea we already talked about 45 00:03:43,388 --> 00:03:48,577 was substitution, where you can just change variables in a known expansion. 46 00:03:48,577 --> 00:03:54,171 So the Taylor series for log of one plus x u, is x minus x squared of two plus x 47 00:03:54,171 --> 00:03:59,158 squared of three, and so forth. and if we just plug in a different value 48 00:03:59,158 --> 00:04:03,403 for x, when wee plug in 1 / N then we get the expansion. 49 00:04:03,403 --> 00:04:07,380 so that's one that technique that we already used. 50 00:04:07,380 --> 00:04:11,380 factoring. A very common thing to do is to estimate 51 00:04:11,380 --> 00:04:15,898 what the leading term is. Then factor that out, and expand the 52 00:04:15,898 --> 00:04:18,342 rest. So, look at this function. 53 00:04:18,342 --> 00:04:19,157 One over n^22+n. + n. 54 00:04:19,157 --> 00:04:23,972 And we'd think to ourselves. What's, what's this going to be, close 55 00:04:23,972 --> 00:04:27,083 to, when n is large? Like, n is a million. 56 00:04:27,083 --> 00:04:32,491 It's going to be close to one over n^2.2. So we might as well factor out the one 57 00:04:32,491 --> 00:04:35,824 over n^2.2. And then, in this case, what we're left 58 00:04:35,824 --> 00:04:40,491 with is 1 / 1 + 1 / n and that's a geometric series. 59 00:04:40,491 --> 00:04:44,437 And we have asymptomatic expansion for geometric series. 60 00:04:44,437 --> 00:04:51,231 So expand it, since it's 1 + 1 / n. It's 1 - 1 / n, + 1 / n^2. 61 00:04:51,231 --> 00:04:56,395 so and we could take that to more terms if we wanted to but that's an 62 00:04:56,395 --> 00:05:01,355 asymptomatic expansion of that. If we use that expansion it, it says that 63 00:05:01,355 --> 00:05:05,363 for n equals 1,000,000. That value's going to be very close to 64 00:05:05,363 --> 00:05:09,644 one over n squared. the relative area be, error that we would 65 00:05:09,644 --> 00:05:13,788 make would be one over n. And that, one over 1,000,000 in that 66 00:05:13,788 --> 00:05:18,473 case, which is probably small enough for our purposes. 67 00:05:18,473 --> 00:05:24,671 you'd distribute that so it's one over N squared - 1 / n^3 + big O of 1 / n to the 68 00:05:24,671 --> 00:05:27,801 4th. That's a asymptotic series in the 69 00:05:27,801 --> 00:05:31,135 standard scale for one over N squared plus N. 70 00:05:31,135 --> 00:05:34,378 very easy to obtain. multiplication. 71 00:05:34,378 --> 00:05:41,987 So multiplication is just algebra and but also employing simplification when we 72 00:05:41,987 --> 00:05:47,468 have smaller terms, we throw them out. So, let's look at the square of the 73 00:05:47,468 --> 00:05:53,364 harmonic numbers so we did an estimate of the harmonic numbers, we talked about the 74 00:05:53,364 --> 00:05:58,597 asymptypes series for the harmonic numbers, it's given by proximation with a 75 00:05:58,597 --> 00:06:04,161 sum and I talked breifly about that and we'll talk more about, about that kind of 76 00:06:04,161 --> 00:06:07,937 asymptotics later. So the harmonic number is approximated 77 00:06:07,937 --> 00:06:13,303 by, log N plus gamma plus big O of one over N, where gamma is, or looks constant 78 00:06:13,303 --> 00:06:16,880 in point.577. So to compute the square of the harmonic 79 00:06:16,880 --> 00:06:19,409 numbers we have. The square though. 80 00:06:19,409 --> 00:06:25,018 So that's two terms with three two factors with three terms each 81 00:06:25,018 --> 00:06:29,904 so we're going to wind up with six factors when we add all that together. 82 00:06:29,904 --> 00:06:35,125 So log N times each one of those, log N squared plus gamma log N, plus big O of 83 00:06:35,125 --> 00:06:39,007 log N over N. inside big O we usually don't specify the 84 00:06:39,007 --> 00:06:44,026 base of the logarithm since it only differs by a constant so it doesn't 85 00:06:44,026 --> 00:06:49,582 matter that it's natural log, so we just write log this means it's not specified 86 00:06:49,582 --> 00:06:55,321 at some constant. Then the next row is gamma times each 87 00:06:55,321 --> 00:06:58,712 one. Gamma*log(n) plus gamma^2 plus O(1/n). 88 00:06:58,712 --> 00:07:03,920 And the next term is O(1/n) times all of them, O(1/n)*log(n). 89 00:07:03,920 --> 00:07:07,486 Over n. Gamma*O(1/n) is O(1/n), and O(1/n)*O(1/n) 90 00:07:07,486 --> 00:07:14,023 is O(1/n^2). So that gives us nine terms, but we can 91 00:07:14,023 --> 00:07:20,947 throw a lot of them out. because well first of all, all the big O 92 00:07:20,947 --> 00:07:27,386 terms you just picked the largest one. so big O of one over N squared is much 93 00:07:27,386 --> 00:07:33,974 smaller than log N over N so it can be subsumed in that, same with O of one over 94 00:07:33,974 --> 00:07:37,574 N. So all the big O terms and and there's 95 00:07:37,574 --> 00:07:42,170 four, five of them, get subsumed in that O of log N over N. 96 00:07:42,170 --> 00:07:48,527 there's the gamma squared and then gamma log N appears twice so that's in 97 00:07:48,527 --> 00:07:55,038 asymptotic series in the standard scale for the square of the harmonic members. 98 00:07:55,038 --> 00:08:01,260 Now just taking a look at this series it's important to note that. 99 00:08:01,260 --> 00:08:06,414 there's a un. a difference between the first couple of 100 00:08:06,414 --> 00:08:09,920 terms and the big O that we lost. So, log N squared. 101 00:08:09,920 --> 00:08:15,992 so n is a, a million [COUGH] log n that's going to be, some small integer, 102 00:08:15,992 --> 00:08:20,040 So log n^22 and 2 of log n is not, they're not that far apart. 103 00:08:20,040 --> 00:08:23,144 so it seems like we're going to need those. 104 00:08:23,144 --> 00:08:27,192 and then gamma^2 is a constant. But log n's a small integer. 105 00:08:27,192 --> 00:08:31,983 it's only a slight improvement in precision to carry on those terms. 106 00:08:31,983 --> 00:08:37,111 And so we're probably going to want those terms but when we get a divided by n, 107 00:08:37,111 --> 00:08:40,620 that's when we have a huge improvement in precision. 108 00:08:40,620 --> 00:08:46,771 Now, you can't always tell ahead of time, how far you have to go, to get this big 109 00:08:46,771 --> 00:08:51,054 improvement. But in real problems, it usually happens 110 00:08:51,054 --> 00:08:56,349 after three or four terms. and it's, and that's what happened here. 111 00:08:56,349 --> 00:09:00,710 If you look at a tables of these quantities for n100 = 100 112 00:09:00,710 --> 00:09:06,870 sorry a 1000, 10,000, and a 100,000 you can see, so h n squared is the quantity 113 00:09:06,870 --> 00:09:13,476 that we're trying to estimate and then, if you just tried to estimate it with log 114 00:09:13,476 --> 00:09:19,346 n squared, you can see you'ld still be off by a fair amount 10% for even a 115 00:09:19,346 --> 00:09:23,692 100,000. if you add the two gamma log in you come 116 00:09:23,692 --> 00:09:30,019 much closer and add the gamma squared actually were accurate to three decimal 117 00:09:30,019 --> 00:09:36,194 places because the next term the one that we're missing is going to differ. 118 00:09:36,194 --> 00:09:42,140 it's going to be bounded by a constant times log n over n n for 100,000. 119 00:09:42,140 --> 00:09:47,319 that's going to be out in the fourth or. The decimal place, assuming the 120 00:09:47,319 --> 00:09:53,570 constant's small which normally we assume it is asymptotic series because they are 121 00:09:53,570 --> 00:09:59,065 but we can check as in this case that that's an accurate approximation. 122 00:09:59,065 --> 00:10:04,767 So usually we'll try to carry it out long enough until we get this big improvement 123 00:10:04,767 --> 00:10:07,608 in precision. Alright, division. 124 00:10:07,608 --> 00:10:11,390 that's like multiplication. so 125 00:10:11,390 --> 00:10:15,256 let's look at this example hn = natural log. 126 00:10:15,256 --> 00:10:20,550 hn over natural log of n1. + 1 so what we'll do for that is we'll 127 00:10:20,550 --> 00:10:24,416 expand the numerator and the denominator both. 128 00:10:24,416 --> 00:10:30,719 and then we'll use the geometric series to expand the denominator. 129 00:10:30,719 --> 00:10:34,500 And that'll give us a multiplication problem. 130 00:10:34,500 --> 00:10:44,680 So let's look at how that works. so [COUGH] h of n is 131 00:10:44,680 --> 00:10:51,139 log n plus gamma + O / 1 / N. That's the approximation that we've been 132 00:10:51,139 --> 00:10:55,984 using for H of N. Natural log of N plus + factor out a log 133 00:10:55,984 --> 00:11:01,674 N, and it becomes natural log of N plus natural log of 1 + 1 / N. 134 00:11:01,674 --> 00:11:06,365 Natural log of 1 + 1 / N is big O of 1 / N 135 00:11:06,365 --> 00:11:11,577 just from Taylor. So now we have the ratio of 2 136 00:11:11,577 --> 00:11:17,372 asymptomatic series. And, what we'll do is factor out the log 137 00:11:17,372 --> 00:11:24,209 end as before, so so let's divide both numerator and 138 00:11:24,209 --> 00:11:32,919 denominator by log n and so the numerator becomes 1 + gamma over log n + of 1 / n 139 00:11:32,919 --> 00:11:38,670 it's over 1 / n log n so we're simplifying that and then 140 00:11:38,670 --> 00:11:43,815 the denominator comes 1 + of 1 / N. We could make it one of 1 over log N. 141 00:11:43,815 --> 00:11:48,779 We're making it a little bit bigger. and, and again, that's just to simplify 142 00:11:48,779 --> 00:11:52,481 the formulas. If we did not get a sufficiently accurate 143 00:11:52,481 --> 00:11:56,251 estimate we could go back and try to correct that. 144 00:11:56,251 --> 00:12:02,241 But now 1 + O of 1 / N, if you expand as a geometric series, it just becomes one 145 00:12:02,241 --> 00:12:07,424 plus, one over one plus O of one over N is one plus O of one over N just as a 146 00:12:07,424 --> 00:12:11,126 geometric series. And again, if there are more terms, you 147 00:12:11,126 --> 00:12:16,882 could carry more terms out there. so now we have a multiplication problem, 148 00:12:16,882 --> 00:12:23,111 and if we mul, multiply that out, that's, a proof that the asymptotic expansion of 149 00:12:23,111 --> 00:12:29,051 HN over log of N plus one, to within of, one over N, is one plus gamma over log N, 150 00:12:29,051 --> 00:12:35,208 plus O of one over N, and again there's a big improvement, in precision when we get 151 00:12:35,208 --> 00:12:41,582 to the one over N term, so this is going to be a very accurate estimate of, that, 152 00:12:41,582 --> 00:12:44,770 more complicated quantity, as N increases. 153 00:12:44,770 --> 00:12:51,583 composition, so this is similar so we're, we're just going to substitute an 154 00:12:51,583 --> 00:12:58,386 expansion and figure out what to do. So if you had to compute e to the h of n 155 00:12:58,386 --> 00:13:05,641 you plug in the expansion for h of n and see what you get what you get is e to the 156 00:13:05,641 --> 00:13:11,320 log n + gamma + O of 1 / n. E to the log n, that's n. 157 00:13:11,320 --> 00:13:16,621 E to the gamma is E to the gamma. That's a constant and then what's left is 158 00:13:16,621 --> 00:13:22,282 E to the big O of 1 / N. And then, that one, you, expand, with 159 00:13:22,282 --> 00:13:26,044 Taylor. Although it's a little, more work to 160 00:13:26,044 --> 00:13:31,361 actually prove that. But you can, from now on, use that lemma. 161 00:13:31,361 --> 00:13:35,368 e to o of one over n is one + zero of n over n. 162 00:13:35,368 --> 00:13:41,994 and then that'll, and you can expand it a couple of terms, if you need to. 163 00:13:41,994 --> 00:13:50,427 and, that gives the simplification that E to the H N is N E to the gamma two of N 164 00:13:50,427 --> 00:13:54,670 one over N or N E to the gamma plus O of one. 165 00:13:54,670 --> 00:13:58,483 And again n e to the gamma that grows with n. 166 00:13:58,483 --> 00:14:04,202 O of one is a constant. So there's a big change in precision so 167 00:14:04,202 --> 00:14:08,810 that's going to be a very accurate approximation for large n. 168 00:14:08,810 --> 00:14:14,798 each time that we do an asymptotic expansion we go down to where we can, 169 00:14:14,798 --> 00:14:20,644 usually we try to go where we can get a big improvement in precision like this. 170 00:14:20,644 --> 00:14:26,205 And gives us a, a simple expression in terms of familiar functions for this 171 00:14:26,205 --> 00:14:30,840 thing, where otherwise it's growth might not be so obvious to see. 172 00:14:30,840 --> 00:14:38,778 and again you can see for n equals a million this is accurate to within one. 173 00:14:38,778 --> 00:14:43,380 absolute one, which is a fine small relative error. 174 00:14:43,380 --> 00:14:49,015 okay. x-log trick so this is a way to bring us 175 00:14:49,015 --> 00:14:56,010 in a position where we can apply the composition in more complicated 176 00:14:56,010 --> 00:15:00,480 scenarios. And, all we'll do is write F of X as. 177 00:15:00,480 --> 00:15:04,761 e to the log of f of x. Then we can expand log of f of x. 178 00:15:04,761 --> 00:15:08,970 And we can expand e to, that series as we did before. 179 00:15:08,970 --> 00:15:13,251 and here's a fine example. One minus one over n to the n. 180 00:15:13,251 --> 00:15:17,823 and when you see a thing like that you, you have to think. 181 00:15:17,823 --> 00:15:22,250 How would you compute that for that large values of n? 182 00:15:22,250 --> 00:15:27,762 ask a programmer where to compute that for N equals 1,000,000 maybe not 183 00:15:27,762 --> 00:15:31,776 necessarily so easy to do. It's going to at least take time 184 00:15:31,776 --> 00:15:37,493 proportionally and, and there might be precision problems or as with factorial, 185 00:15:37,493 --> 00:15:41,780 there might be problems in needing to carry too many digits. 186 00:15:41,780 --> 00:15:47,224 well actually the way people compute things like that is use the X log trick 187 00:15:47,224 --> 00:15:52,260 so that is we write that as E to the log of 1 - 1 / N to the N. 188 00:15:52,260 --> 00:15:58,674 and so the log of 1 / -1 to the N. We can bring the N down. 189 00:15:58,674 --> 00:16:06,840 it is N times the log of 1 - 1 / N. so now if we expand log of 1 - 1 / N 190 00:16:06,840 --> 00:16:13,770 again, using the Taylor series, we get -1 / N plus O of 1 over N^2. 191 00:16:13,770 --> 00:16:16,906 And then do the algebra. That's e^-1-1)+O(1/n). 192 00:16:16,906 --> 00:16:19,335 + O of 1 / N. And again, eO(1/n) to the O of 1 /O(1/n). 193 00:16:19,335 --> 00:16:23,484 N that's 1 + O / N so that's 1/e. It says that, that function, 1-(1/n)^n, 194 00:16:23,484 --> 00:16:30,871 is going to be very close to 1/e. And again, that's the big improvement in 195 00:16:30,871 --> 00:16:37,043 precision we always look for. And again, we can check that for 196 00:16:37,043 --> 00:16:37,246 n1,000,000. = 1,000,000. 197 00:16:37,246 --> 00:16:44,835 That's accurate to six decimal places. Because the O says that the error is 198 00:16:44,835 --> 00:16:50,207 going to be out there around the six decimal place. 199 00:16:50,207 --> 00:16:58,480 so again when we're trying to understand what the value of the quantity is if we 200 00:16:58,480 --> 00:17:05,518 know it's 1 / e which is this constant of 367879. that's very precise and concise 201 00:17:05,518 --> 00:17:12,160 information as opposed to that exact expression which maybe it's hard to know 202 00:17:12,160 --> 00:17:15,999 what it is. and when we start combining these kinds 203 00:17:15,999 --> 00:17:21,179 of formulas which we do all the time we're going to want to work with the 204 00:17:21,179 --> 00:17:26,744 precise and concise expressions. so that's the X-log technique, and we 205 00:17:26,744 --> 00:17:33,267 actually use that one quite a bit. so thinking about these various 206 00:17:33,267 --> 00:17:38,820 techniques here's just a couple more examples 207 00:17:38,820 --> 00:17:44,645 that you might want to try doing to make sure that you understand the kinds of 208 00:17:44,645 --> 00:17:50,545 techniques that we're using. so log of N over N - two, 2 with N, 1 / 209 00:17:50,545 --> 00:17:57,302 N^2 and HN^2 what's that constant times the one over N term, because we only got 210 00:17:57,302 --> 00:18:01,277 it to log, log N over N. And that's just to illustrate that if 211 00:18:01,277 --> 00:18:04,275 desired we can go to more asymptotic accuracy. 212 00:18:04,275 --> 00:18:09,554 maybe we need to do that because we've got a function where we're multiplying 213 00:18:09,554 --> 00:18:13,400 that thing by N squared and so we need more accuracy. 214 00:18:13,400 --> 00:18:18,963 just for example. so for log N minus two what we do is 215 00:18:18,963 --> 00:18:23,178 factor out the N so that's the leading term. 216 00:18:23,178 --> 00:18:29,500 And then we have log of 1 - 2 / N and then just expand the rest. 217 00:18:29,500 --> 00:18:36,541 and so it's - 2 over N plus big of one over N squared [COUGH], so, that's the 218 00:18:36,541 --> 00:18:42,653 solution to that one, and this one is, just, carrying out the asymptotic 219 00:18:42,653 --> 00:18:48,921 approximations to one more term, which is, one over N squared term, and then 220 00:18:48,921 --> 00:18:52,790 that gives the coefficient of log N over N is one. 221 00:18:52,790 --> 00:18:59,770 and again these types of things with as with any kind of mathematics require 222 00:18:59,770 --> 00:19:05,888 little bit of practice but the, the techniques are, are so simple its not 223 00:19:05,888 --> 00:19:10,672 difficult to learn how it do these kinds of expansions. 224 00:19:10,672 --> 00:19:16,320 so that's a quick introduction to manipulating asymptotic expansions.