1
00:00:03,360 --> 00:00:06,148
Today we're going to talk about 
asymptotics. 

2
00:00:06,148 --> 00:00:11,112
this is mathematics that was developed 
well, well before the advent of 

3
00:00:11,112 --> 00:00:14,920
computers. 
in the 18th and 19th centuries. 

4
00:00:14,920 --> 00:00:19,884
but it's quite relevant to the analysis 
of algorithms and to analytic 

5
00:00:19,884 --> 00:00:23,692
combinatorics. 
we'll start of by talking about the 

6
00:00:23,692 --> 00:00:28,112
standard asymptotics scale. 
So the goal is to develop concise and 

7
00:00:28,112 --> 00:00:33,484
accurate expressions that give us good 
estimates of the quantities we're 

8
00:00:33,484 --> 00:00:37,360
interested in studying. 
as I mentioned in the first. 

9
00:00:37,360 --> 00:00:43,385
The lectures the big-oh notation is 
really not adequate for this if you say 

10
00:00:43,385 --> 00:00:49,410
big-oh of log N, it doesn't give you an 
accurate measure of the, of the quantity 

11
00:00:49,410 --> 00:00:55,794
it's on upper bound and it's within a 
constant factor and there's no way to get 

12
00:00:55,794 --> 00:00:59,309
a precise estimate of of what the 
quantity is. 

13
00:00:59,309 --> 00:01:05,908
if we had take a definition like this say 
H of N for the harmonic numbers that 

14
00:01:05,908 --> 00:01:11,360
one's accurate but it's not concise take, 
it's going to take time to compute. 

15
00:01:11,360 --> 00:01:16,958
the exact value that you want. 
Now that, that's not too bad but still 

16
00:01:16,958 --> 00:01:22,782
the spirit of what we're talking about is 
to try to get accurate and concise 

17
00:01:22,782 --> 00:01:27,321
expressions like this one. 
natural log N plus gamma plus big-oh of 

18
00:01:27,321 --> 00:01:31,180
one over N so that one for large values 
of N. 

19
00:01:31,180 --> 00:01:36,604
will give, a numerical result that's, 
very close to the, quantity that we're 

20
00:01:36,604 --> 00:01:40,578
interested in studying. 
And we'll see lots and lots of examples. 

21
00:01:40,578 --> 00:01:45,120
But that the, basic goal. 
we want concise and accurate estimates of 

22
00:01:45,120 --> 00:01:48,085
the quantities, we're interested in 
studying. 

23
00:01:48,085 --> 00:01:51,933
Now, we won't go, crazy with defining 
what concise means. 

24
00:01:51,933 --> 00:01:56,348
what, what I mean by it is, I've got 
standard functions, and I've got 

25
00:01:56,348 --> 00:02:00,764
constants that are maybe known. 
and I want to be able to compute this 

26
00:02:00,764 --> 00:02:03,539
value for large N. 
it's as simple as that. 

27
00:02:03,539 --> 00:02:08,567
And I want to write a program we use a 
calculator to compute the value. And 

28
00:02:08,567 --> 00:02:13,680
actually that, that kind of definition 
it's easy to understand the motivation 

29
00:02:13,680 --> 00:02:19,495
for a scientist in the 18th and 19th 
centuries who were learning more about 

30
00:02:19,495 --> 00:02:24,608
mathematical models the world, in coming 
up with functions that describe what 

31
00:02:24,608 --> 00:02:29,529
there, what ever they're interested in 
studying. But they wanted to be able to 

32
00:02:29,529 --> 00:02:34,770
do calculations, in order to be able to 
compare their hypothesis with what goes 

33
00:02:34,770 --> 00:02:39,986
on in the mathematic, in the natural 
world. And without asymptotics it would 

34
00:02:39,986 --> 00:02:45,562
be hard to do so because without 
computers you definitely need to be able 

35
00:02:45,562 --> 00:02:50,197
to compute your answer. 
And that's always a good perspective to 

36
00:02:50,197 --> 00:02:54,900
have in the back of our minds when we're 
thinking about asymptotics. 

37
00:02:54,900 --> 00:03:01,593
so, this is just, reminder, I talked 
about these notations, earlier on, so, 

38
00:03:01,593 --> 00:03:08,211
the big, bigger notation for upper bands, 
if you say G of N equals bigger graph of 

39
00:03:08,211 --> 00:03:11,406
N. 
That means absolute value of a ratio is 

40
00:03:11,406 --> 00:03:18,100
bounded from above as N goes to infinity. 
and we are going to use that notation, 

41
00:03:18,100 --> 00:03:21,979
for error terms but not for, our, our 
leading terms. 

42
00:03:21,979 --> 00:03:26,620
also we use, a little-oh notation which 
says that 

43
00:03:26,620 --> 00:03:31,864
G of N, is little-oh of F of N, if the 
ratio tends to zeros and approachs 

44
00:03:31,864 --> 00:03:36,046
infinity so that's GN's asymptotically 
smaller than F of N. 

45
00:03:36,046 --> 00:03:41,503
And again, we use that for error terms, 
in fact, often we use this, so called 

46
00:03:41,503 --> 00:03:47,173
Pildon notation, which just says, that G 
of N and F of N ratio approachs one as N 

47
00:03:47,173 --> 00:03:51,710
approachs infinity, that's the weakest 
non trivial little-oh. 

48
00:03:51,710 --> 00:03:56,274
so 
We use those notations to come up with, 

49
00:03:56,274 --> 00:04:00,838
approximations, 
So, if we say that G of N equals F of N 

50
00:04:00,838 --> 00:04:05,671
plus big-oh of H of N. 
It means the error will be within, at 

51
00:04:05,671 --> 00:04:09,683
most, a constant factor. 
Of H of N, as N increases. 

52
00:04:09,683 --> 00:04:15,073
A little-oh means that we know the error 
will decrease as N increases. 

53
00:04:15,073 --> 00:04:19,526
And that's good. 
That, means that for larger N we get a 

54
00:04:19,526 --> 00:04:24,057
better result. 
Intelda again, is the weakest non trivial 

55
00:04:24,057 --> 00:04:27,963
little-oh .. 
As N increases we expect a better result. 

56
00:04:27,963 --> 00:04:34,682
And that's, the, basic, approximations 
that we're going to be trying to develop. 

57
00:04:34,682 --> 00:04:39,760
so now with that background, what we're 
looking at is 

58
00:04:39,760 --> 00:04:46,318
Developing a series of functions, and if 
we have a series of functions Gk with Gk 

59
00:04:46,318 --> 00:04:52,721
plus one equal little o of Gk so that's a 
decreasing an asymptotically decreasing 

60
00:04:52,721 --> 00:04:59,197
series of functions, then if we write. 
Fn as the linear combination of those as 

61
00:04:59,197 --> 00:05:03,600
they decrease. 
We call that an asymptotic expansion of 

62
00:05:03,600 --> 00:05:08,084
the function f. 
And since the functions decrease the 

63
00:05:08,084 --> 00:05:14,281
expansion is supposed to get more 
accurate as we add more and more terms. 

64
00:05:14,281 --> 00:05:20,641
Precisely, it represents the collection 
of formula f of n is big-oh of G sub 

65
00:05:20,641 --> 00:05:24,554
zero. 
It's also C0 G0 plus big-oh of G sub one 

66
00:05:24,554 --> 00:05:28,876
and, and so forth. 
And we can pick off of this list of 

67
00:05:28,876 --> 00:05:32,554
formulas. 
the one that suits are purposes best, in 

68
00:05:32,554 --> 00:05:37,896
terms of, getting, an accurate estimate 
of the quantity we're looking at, and 

69
00:05:37,896 --> 00:05:42,348
this will become more clear, when we look 
at specific examples. 

70
00:05:42,348 --> 00:05:47,690
so we're using big-oh notation, but in 
the specific technical sense we want to 

71
00:05:47,690 --> 00:05:53,100
be able to be insured that we can get 
more accurate asymptotic estimates, if 

72
00:05:53,100 --> 00:05:58,159
needed. 
so the standard scale we use the 

73
00:05:58,159 --> 00:06:03,227
functions gk we use. 
Powers of n and logn and maybe logn and 

74
00:06:03,227 --> 00:06:08,208
Log, Log N N exponentials. 
so those are the st, standard functions 

75
00:06:08,208 --> 00:06:12,395
that we want to use. 
And we'll see it's very easy to express 

76
00:06:12,395 --> 00:06:17,953
many of the functions that arise in 
scientific studies in terms of the 

77
00:06:17,953 --> 00:06:22,429
standard scale. 
and we'll give it, it's not necessary to 

78
00:06:22,429 --> 00:06:27,626
give a detailed definition of this. 
So typically, what happens is, we only 

79
00:06:27,626 --> 00:06:32,968
use a few terms, maybe two, three or four 
terms, a second, or third or fourth 

80
00:06:32,968 --> 00:06:37,730
equation from this. 
when the unused terms are extremely 

81
00:06:37,730 --> 00:06:42,949
small, that's when we stop. 
because we have the big-oh estimate that 

82
00:06:42,949 --> 00:06:48,455
says, we're within, a constant of that 
unused term, and it's extremely small, 

83
00:06:48,455 --> 00:06:50,795
relatively. 
That's when we stopped. 

84
00:06:50,795 --> 00:06:54,374
[COUGH]. 
So we use the tilda notation if we don't 

85
00:06:54,374 --> 00:06:57,884
want to bother carrying around the big-oh 
information. 

86
00:06:57,884 --> 00:07:03,459
And a lot of times, that simplifies the 
calculations, and there's no reason not 

87
00:07:03,459 --> 00:07:06,556
to. 
We usually check our asymptotic estimates 

88
00:07:06,556 --> 00:07:12,269
against, the actual values, to make sure, 
that what we have is giving us the 

89
00:07:12,269 --> 00:07:16,702
accuracy that we want. 
And if we do mathematically want to 

90
00:07:16,702 --> 00:07:22,890
specify information on the unused terms, 
we go ahead and do that using the big-oh 

91
00:07:22,890 --> 00:07:28,175
notation or the little O notation. 
But the main point is that the methods we 

92
00:07:28,175 --> 00:07:32,070
use in principle should extend to any 
desired precision. 

93
00:07:32,070 --> 00:07:38,107
if we need more terms we can get them. 
And that's a very big difference from the 

94
00:07:38,107 --> 00:07:42,769
use of the big-oh notation. 
in the theory of algorithms where it's 

95
00:07:42,769 --> 00:07:47,693
both expressing an upper bound and 
capturing the concept of the worst case. 

96
00:07:47,693 --> 00:07:53,471
This is more in the spirit of of, of 
science in the origins are clear in the 

97
00:07:53,471 --> 00:07:59,118
eighteenth and 19th centuries where 
people wanted to be able to calculate 

98
00:07:59,118 --> 00:08:04,108
things and then compare those with the 
results of scientific experiments. 

99
00:08:04,108 --> 00:08:08,048
And that's what we want to do in the 
analysis of algorithms. 

100
00:08:08,048 --> 00:08:12,288
and that's why. 
we embrace all of this classical 

101
00:08:12,288 --> 00:08:16,566
mathematics. 
so here's an example from that w, we 

102
00:08:16,566 --> 00:08:20,935
looked at in the second lecture. 
so there's 

103
00:08:20,935 --> 00:08:27,687
We came up against a theorem that was 
going to give us coefficient abstraction 

104
00:08:27,687 --> 00:08:31,421
for. 
This was for solving linear recurrences. 

105
00:08:31,421 --> 00:08:38,412
and eventually we found through the use 
of generating functions that the quantity 

106
00:08:38,412 --> 00:08:44,290
that we're interested in is the 
coefficient of z to the n in the ratio of 

107
00:08:44,290 --> 00:08:47,230
two polynomials. 
and so what we. 

108
00:08:47,230 --> 00:08:53,284
Can do with asymptotics is take a pretty 
complicated theorem statement. 

109
00:08:53,284 --> 00:09:00,157
that I'll show in just a second. 
And reduce it down to actually a pretty 

110
00:09:00,157 --> 00:09:04,739
general result. 
The coefficient of z to the n in the two, 

111
00:09:04,739 --> 00:09:10,957
ratio of the two polynomials is 
asymptotic to a constant times beta bn, n 

112
00:09:10,957 --> 00:09:17,094
to the [INAUDIBLE] minus one. 
Where beta is the smallest modulis root 

113
00:09:17,094 --> 00:09:21,640
of that 
Polynomial in, in the dom, denominator in 

114
00:09:21,640 --> 00:09:27,491
new is its multiplicity. 
So this is just picking the leading term 

115
00:09:27,491 --> 00:09:33,184
offer the more detailed theorem. 
so in lecture two I gave this detail 

116
00:09:33,184 --> 00:09:40,379
theorem that show that the coefficient of 
Z to the N in that ratio there's a term 

117
00:09:40,379 --> 00:09:44,333
called corresponding to each zero of G of 
Z. 

118
00:09:44,333 --> 00:09:51,053
and then according to its multiplicity. 
And the, with [INAUDIBLE] can we can not 

119
00:09:51,053 --> 00:09:55,365
worry about 
All the smaller terms in that sum, and 

120
00:09:55,365 --> 00:10:00,320
just pick out the large, largest one in a 
precise, technical sense. 

121
00:10:00,320 --> 00:10:07,486
so for example if the roots are three and 
two then it might be three to the n and 

122
00:10:07,486 --> 00:10:13,432
three to the n plus two to the n. 
Then you can see as n gets even to eleven 

123
00:10:13,432 --> 00:10:18,540
they're pretty close. 
and when n gets very high, they're going 

124
00:10:18,540 --> 00:10:23,419
to get closer and closer. 
so usually, the, the pole of smallest 

125
00:10:23,419 --> 00:10:26,240
modulus really dominates. 
so no. 

126
00:10:26,240 --> 00:10:32,012
Question three to the N plus two to the N 
is asymptotic to three to the N. 

127
00:10:32,012 --> 00:10:35,760
You can forget about the two to the N for 
large N. 

128
00:10:35,760 --> 00:10:40,369
and [COUGH]. 
in fact the convergence is exponentially 

129
00:10:40,369 --> 00:10:47,480
fast as N gets large even by one the, it, 
it gets closer and closer to being 

130
00:10:47,480 --> 00:10:51,332
accurate. 
the ratio gets closer and closer to one. 

131
00:10:51,332 --> 00:10:57,035
So usually that, that poll of smallest 
modalist, the the place where the 

132
00:10:57,035 --> 00:11:02,517
denominator goes zero closest to the 
origin, that's the one that really 

133
00:11:02,517 --> 00:11:05,850
matters. 
And I emphasize this because this 

134
00:11:05,850 --> 00:11:11,110
particular scenario turns to be very 
important in a general context. 

135
00:11:11,110 --> 00:11:16,245
Later on, in analytic combinatorics. 
Now there are situations, depending on 

136
00:11:16,245 --> 00:11:20,276
what these polynomials are, where the 
poles are close together. 

137
00:11:20,276 --> 00:11:24,762
or, the multiple poles very close to the 
one of smaller modulus. 

138
00:11:24,762 --> 00:11:31,132
And so in those kinds of cases, we have 
to figure out how to extract, the leading 

139
00:11:31,132 --> 00:11:34,383
terms. 
But still, it's very important to realize 

140
00:11:34,383 --> 00:11:37,828
that we don't need to carry around, the 
small ones. 

141
00:11:37,828 --> 00:11:41,339
So, sure. 
If it, if one of the roots is, two, and 

142
00:11:41,339 --> 00:11:45,110
the other one is one half. 
And the other is one over 1.999. 

143
00:11:45,110 --> 00:11:48,123
And nine. 
it's not going to be that close. 

144
00:11:48,123 --> 00:11:52,848
You'd be off by a factor of two if you 
try to throw that one away. 

145
00:11:52,848 --> 00:11:58,806
but it's easy to figure that out, and 
it's important to know that it's easy to 

146
00:11:58,806 --> 00:12:03,805
throw away the small ones. 
so here's how analysis would go for a 

147
00:12:03,805 --> 00:12:09,215
recurrence, say like one of the earlier 
recurrences that we started out with. 

148
00:12:09,215 --> 00:12:13,050
A sub N equals five. 
An minus one minus six, AN minus two. 

149
00:12:13,050 --> 00:12:16,269
And A zero equals zero and A one equals 
one. 

150
00:12:16,269 --> 00:12:18,540
So 
Not to 

151
00:12:18,540 --> 00:12:23,400
We only worry about the 
The. 

152
00:12:23,400 --> 00:12:28,790
[COUGH] Root of G that's smallest. 
so to solve the recurrence we make it 

153
00:12:28,790 --> 00:12:35,147
valid for all N then we multiply by Z and 
sum on N to get a polynomial and that 

154
00:12:35,147 --> 00:12:39,778
gives us for the generating function a 
ratio of two polynomials. 

155
00:12:39,778 --> 00:12:44,615
And what we're interested in is the 
coefficient of Z to the N in that 

156
00:12:44,615 --> 00:12:49,245
generating function. 
And now we can just plug and chug in the 

157
00:12:49,245 --> 00:12:52,769
theorem. 
smallest root of the denominator is one 

158
00:12:52,769 --> 00:12:57,400
third, so it's going to be asymptotic to 
three to the N and then we. 

159
00:12:57,400 --> 00:13:01,214
Go ahead and calculate the constant. 
And if you plug in the values for the 

160
00:13:01,214 --> 00:13:03,380
constant in that formula you just get 
one. 

161
00:13:03,380 --> 00:13:08,593
And if you want to apply the same thing 
to say, the recurrence for the Fibonacci 

162
00:13:08,593 --> 00:13:11,656
numbers. 
Again, the same steps are going to work. 

163
00:13:11,656 --> 00:13:15,827
In that case, the constant will be 
1/sqrt(5), and it will be phi^n, the 

164
00:13:15,827 --> 00:13:19,802
golden ratio to the n. 
The extra term in that case is phi hat, 

165
00:13:19,802 --> 00:13:22,800
which is less than one and totally 
negligible. 

166
00:13:22,800 --> 00:13:30,951
So with acentonics we get a relatively 
simple, general theorem that gives us a 

167
00:13:30,951 --> 00:13:36,480
precise and concise result for a big 
family of problems. 

168
00:13:36,480 --> 00:13:42,559
okay, so back to the basics, where do we 
start out, where do we get the asymptotic 

169
00:13:42,559 --> 00:13:47,719
expansions, that we need to start out. 
Well for a lot of the generating 

170
00:13:47,719 --> 00:13:53,444
functions that arise, Taylors thorem 
immediately, gives us an answer, it's, 

171
00:13:53,444 --> 00:13:58,675
expansion through power series and 
Taylors thorem they're infinite, but, 

172
00:13:58,675 --> 00:14:03,976
since they converge, you, it can stop at 
any point, to give results like this. 

173
00:14:03,976 --> 00:14:10,126
In principal we can take as many turns as 
we want off the, infinite series, and 

174
00:14:10,126 --> 00:14:13,549
then. 
We have [COUGH] a asymptotic series in 

175
00:14:13,549 --> 00:14:18,114
the standard scale. 
So again, these are just immediate from 

176
00:14:18,114 --> 00:14:23,308
Taylor's Theorem, where the term of Xn/n! 
of N, Is the nth derivative of the 

177
00:14:23,308 --> 00:14:26,929
function. 
So we looked at all of these when we 

178
00:14:26,929 --> 00:14:30,392
talked about expanding generating 
functions. 

179
00:14:30,392 --> 00:14:36,688
The difference now is with asymptotics, 
we're only interested in taking a couple 

180
00:14:36,688 --> 00:14:42,040
of terms for the purpose of being able to 
accurately compute values. 

181
00:14:42,040 --> 00:14:47,593
So those are standard examples. 
Now these are Taylor's Theorem just for X 

182
00:14:47,593 --> 00:14:51,259
goes to zero. 
Actually we're usually interested in 

183
00:14:51,259 --> 00:14:56,724
coefficient Z to the N as in increases, 
so what we'll do is just substitute one 

184
00:14:56,724 --> 00:15:03,158
over n in all of these formulas to get 
asymptotic expansions and these are maybe 

185
00:15:03,158 --> 00:15:08,554
in more familiar terms, if you wanted to 
compute e to the one over N, say for N 

186
00:15:08,554 --> 00:15:13,190
equals 1,000,000 this will tell you it's 
going to be pretty close to one. 

187
00:15:13,190 --> 00:15:18,124
That'll be one plus one over a million 
plus one over two times a million 

188
00:15:18,124 --> 00:15:21,977
squared. 
that kind of be worth trying to compute 

189
00:15:21,977 --> 00:15:27,182
that any more accurately than that. 
this will give the very great accuracy 

190
00:15:27,182 --> 00:15:32,048
just with a few terms. 
same log of one over one plus one over N 

191
00:15:32,048 --> 00:15:37,118
for N, N equals a million. 
That's pretty close to one millionth the 

192
00:15:37,118 --> 00:15:42,390
next term you will notice until twelve 
decimal places out and the next one 

193
00:15:42,390 --> 00:15:46,716
eighteen decimal places out. 
If you just wanted to a few decimal 

194
00:15:46,716 --> 00:15:49,126
places. 
use one over a million. 

195
00:15:49,126 --> 00:15:56,128
That's the whole idea of asymptotics. and 
a binomial has this is for K constant 

196
00:15:56,128 --> 00:16:02,832
we'll have a similar kind of character. 
now this gets more complicated if K grows 

197
00:16:02,832 --> 00:16:08,270
with N and that's, be one of the things 
that we'll talk about later on. 

198
00:16:08,270 --> 00:16:15,075
the one that we use really most often is 
a geometric so anyway that's the what you 

199
00:16:15,075 --> 00:16:20,006
get when you plug in one over N in the 
straight geometric series. 

200
00:16:20,006 --> 00:16:25,354
One over N minus, what it says is one 
over N minus one is really close to one 

201
00:16:25,354 --> 00:16:30,632
over N for a million. 
again next term out wouldn't happen for 

202
00:16:30,632 --> 00:16:35,454
twelve decimal places. 
so those are basic building blocks of the 

203
00:16:35,454 --> 00:16:42,900
asymptotics expansions that we work with. 
so just as exercises just using those 

204
00:16:42,900 --> 00:16:49,805
simple formulas then we can get 
relatively accurate approximations of 

205
00:16:49,805 --> 00:16:55,924
say, sums and differences of functions. 
just using those formulas. 

206
00:16:55,924 --> 00:17:03,004
And so it's worthwhile to take a look at 
these exercises, and not just as getting, 

207
00:17:03,004 --> 00:17:09,472
getting started a problem in asymptotics. 
we specify the function and then we 

208
00:17:09,472 --> 00:17:12,910
specify how accurately we want to 
estimate it. 

209
00:17:12,910 --> 00:17:16,721
and so 
so these two problems, it's definitely 

210
00:17:16,721 --> 00:17:20,382
worthwhile just working for a second on 
those. 

211
00:17:20,382 --> 00:17:26,286
And if you go ahead and just, plug in 
from the formula, from before, the 

212
00:17:26,286 --> 00:17:30,321
previous slide. 
log of one plus one over N is one over N 

213
00:17:30,321 --> 00:17:33,011
minus one over 2N2 squared plus one 
big-oh of one over N3. 

214
00:17:33,011 --> 00:17:35,477
cube. 
N log of N minus one over N is minus one 

215
00:17:35,477 --> 00:17:38,615
over N, 
and so the one over N terms cancel. 

216
00:17:38,615 --> 00:17:43,217
and then you have two, one over two N 
squared terms which makes it just minus 

217
00:17:43,217 --> 00:17:46,060
one over N squared plus big-oh, one over 
N cubed. 

218
00:17:46,060 --> 00:17:52,324
So right away you can see the log of one 
plus one over N is a rather complicated 

219
00:17:52,324 --> 00:17:58,040
function but we can approximate it very 
accurately as just minus one over N 

220
00:17:58,040 --> 00:18:04,070
squared and that's going to be quite 
accurate for in in the practical ranges 

221
00:18:04,070 --> 00:18:08,298
of interest. 
If it's minus than what happen is the one 

222
00:18:08,298 --> 00:18:13,310
over N squared terms cancel out we're 
just left with two over N. 

223
00:18:13,310 --> 00:18:20,754
so that's just a simple, simple example 
of asymptotic expansions using the basic 

224
00:18:20,754 --> 00:18:24,601
information that we get from Taylor's 
theorem. 

225
00:18:24,601 --> 00:18:31,209
[COUGH] and then combining those results 
really just using algebra. 

226
00:18:31,209 --> 00:18:39,323
and for lots and lots of functions that 
come up we can apply techniques like this 

227
00:18:39,323 --> 00:18:44,760
to develop accurate expansions. 
that's what we'll look at next.