1
00:00:03,640 --> 00:00:08,768
Next, we're going to take a look at 
techniques for dealing with coming up 

2
00:00:08,768 --> 00:00:13,896
with asymptotic expansions when our 
quantities are expressed in terms of 

3
00:00:13,896 --> 00:00:17,408
sums. 
and we, we'll see lots and lots of need 

4
00:00:17,408 --> 00:00:22,396
for applying these techniques. 
A lot of times, our final result is in 

5
00:00:22,396 --> 00:00:27,173
form, in the form of a sum and, so what 
we need to, in, in the, 

6
00:00:27,173 --> 00:00:32,582
Maybe the terms at the end of the sum are 
much smaller than the terms at the 

7
00:00:32,582 --> 00:00:37,640
beginning, so, we have to, use different 
techniques for different, 

8
00:00:37,640 --> 00:00:43,152
different ranges of the sum. 
So here's a, an easy example called 

9
00:00:43,152 --> 00:00:48,498
bounding the tail. 
So there's a famous problem where the end 

10
00:00:48,498 --> 00:00:52,507
result is expressed in terms of this 
finite sum. 

11
00:00:52,507 --> 00:00:57,078
N factorial, 
sm as K goes from zero to N minus one to 

12
00:00:57,078 --> 00:01:02,347
the K over K factorial. 
So to deal with that one what we're going 

13
00:01:02,347 --> 00:01:09,995
to do is write it as an infinite sum so 
the infinite sum K greater than equal to 

14
00:01:09,995 --> 00:01:13,582
zero. 
Minus one to the K over K factorial, 

15
00:01:13,582 --> 00:01:19,996
that's just one over E, E to the minus 
one. So that quantity that we're 

16
00:01:19,996 --> 00:01:26,585
interested in is equal to, N factorial 
over E, minus this remainder term, and 

17
00:01:26,585 --> 00:01:33,877
the remainder term is N factorial sum K 
bigger than N, minus one to the K over K, 

18
00:01:33,877 --> 00:01:41,520
K factorial. So now what we can do is 
just see the this, infinite sum, we can 

19
00:01:41,520 --> 00:01:47,329
bound it just absolutely it's, 
The first terms left someone over N plus 

20
00:01:47,329 --> 00:01:52,579
one, the next ones left someone over N 
plus one squared, like that, which is 

21
00:01:52,579 --> 00:01:57,049
just one over N. 
so that's a proof that, that infinite sum 

22
00:01:57,049 --> 00:02:02,796
is just one over N, and that's just to 
proof that are original problem is N 

23
00:02:02,796 --> 00:02:08,330
factorial over E to within big-oh of one 
over N, and again N factorial grows so 

24
00:02:08,330 --> 00:02:14,148
fast that's an extremely accurate 
estimate of that sum, so that happens a 

25
00:02:14,148 --> 00:02:20,090
lot the tail is very small. 
All and we can bound the whole tail at 

26
00:02:20,090 --> 00:02:25,068
once. 
another, possibility is that, actually 

27
00:02:25,068 --> 00:02:32,632
the, terms and the sum are rapidly 
increasing, in that case, it might be 

28
00:02:32,632 --> 00:02:37,708
that, the only term that matters is the 
last one. 

29
00:02:37,708 --> 00:02:45,512
For example, some of, K of K factorial. 
so if you just look at the last two terms 

30
00:02:45,512 --> 00:02:51,565
of that sum, those are n factorial + n 
-one factorial, all the rest of them are 

31
00:02:51,565 --> 00:02:55,547
all less than one over ten - one is n - 
one of them. 

32
00:02:55,547 --> 00:02:59,450
To that gives it to within a big-oh of 
one over N. 

33
00:02:59,450 --> 00:03:05,958
So, we have to have a feeling for, how 
the sum grows, where the big terms are, 

34
00:03:05,958 --> 00:03:11,252
where the small terms are. 
But, often the sums arise the terms 

35
00:03:11,252 --> 00:03:18,629
change in a way that we can take, the, we 
can find the most significant part of the 

36
00:03:18,629 --> 00:03:25,311
answer and express that in and bound the 
rest of it to get our asymptotic 

37
00:03:25,311 --> 00:03:30,733
expansion. 
the other thing that we do quite often is 

38
00:03:30,733 --> 00:03:37,973
approximate with an integral and as I 
mentioned that's where our approximations 

39
00:03:37,973 --> 00:03:44,808
for the harmonic numbers and the 
factorials or the stirling numbers come 

40
00:03:44,808 --> 00:03:48,842
from. 
and we talked about those approximations 

41
00:03:48,842 --> 00:03:55,078
and there's proofs of these simple things 
but we'll talk about better 

42
00:03:55,078 --> 00:04:00,433
approximations u, later on. 
So, now those are three basic terms that 

43
00:04:00,433 --> 00:04:07,549
we use for approximating finite sums but 
the main one is approximating with an 

44
00:04:07,549 --> 00:04:10,690
integral. 
the [COUGH] classic formula for 

45
00:04:10,690 --> 00:04:16,556
approximating sums within the goals is 
known as Euler-Maclaurin summation and 

46
00:04:16,556 --> 00:04:22,837
there's two versions of that theorem 
given in the book and a bit of discussion 

47
00:04:22,837 --> 00:04:28,221
about where it comes from most people are 
just going to be in the position of 

48
00:04:28,221 --> 00:04:31,810
wanting to apply the theorem. 
So I have a finite sum. 

49
00:04:31,810 --> 00:04:38,671
say K goes from one to N of F of K. 
that's this theorum gives an asymptotic 

50
00:04:38,671 --> 00:04:43,817
series for that sum. 
kind of like a Taylor expansion that is 

51
00:04:43,817 --> 00:04:47,950
expressed in terms of the derivitive of 
the function. 

52
00:04:47,950 --> 00:04:54,185
there's a couple of unique things about 
the about the series when it comes to 

53
00:04:54,185 --> 00:04:58,416
applying it. 
So one thing is that the error correction 

54
00:04:58,416 --> 00:05:04,281
terms, what are they like? 
the first one is half f of n so that's at 

55
00:05:04,281 --> 00:05:09,031
the end of the integral there's a little 
bit left out say. 

56
00:05:09,031 --> 00:05:13,560
And then there's a constant that's 
dependent on the function. 

57
00:05:13,560 --> 00:05:19,640
Sometimes we have explicit expression for 
this constant sometimes we don't. 

58
00:05:19,640 --> 00:05:24,500
And actually the two cases we gave for 
harmonic numbers. 

59
00:05:24,500 --> 00:05:30,663
We just name that thing gamma. 
We don't know how to express it in terms 

60
00:05:30,663 --> 00:05:35,871
of other mathematical constants. 
For factorials, for Stirling 

61
00:05:35,871 --> 00:05:40,732
Approximation of logn!), of N factorial 
it turns out that, that constant is 

62
00:05:40,732 --> 00:05:41,166
square2*pi). 
root of 2 Pi. 

63
00:05:41,166 --> 00:05:46,200
But that's something that has to be 
derived independently. 

64
00:05:46,200 --> 00:05:52,214
And then the next error terms, the first 
one is the proportional to the first 

65
00:05:52,214 --> 00:05:58,093
derivative of the function with 
coefficient 112 and then usually, we stop 

66
00:05:58,093 --> 00:06:03,079
there because the next one is 
proportional to the third derivative 

67
00:06:03,079 --> 00:06:07,024
with, constant of one over 720, so it's 
way smaller. 

68
00:06:07,024 --> 00:06:12,828
Actually this series, like some other 
asymptotic series, doesn't neccesarily 

69
00:06:12,828 --> 00:06:19,005
converge, the terms could start start to 
get bigger so we don't want to take to 

70
00:06:19,005 --> 00:06:24,174
many, but we can know that. 
[COUGH] since it's an asymptotic series, 

71
00:06:24,174 --> 00:06:29,752
if we stop with a big-oh O we can get an 
accurate result by stopping with just a 

72
00:06:29,752 --> 00:06:34,112
few terms, and usually, for 
Euler–Maclaurin summation, we have the 

73
00:06:34,112 --> 00:06:39,819
inner goal in just a few more terms so 
there's a lot of details about that in a 

74
00:06:39,819 --> 00:06:45,654
book but in terms of applying it just 
using this form is very useful for a lot 

75
00:06:45,654 --> 00:06:51,421
of applications. 
So classic example F of K equals one over 

76
00:06:51,421 --> 00:06:58,420
K, integral of F of X DX for one to N is 
log N and then 

77
00:06:58,420 --> 00:07:01,595
the Fn) of N is one over N, so that's a 
one over 2N. 

78
00:07:01,595 --> 00:07:07,417
The constant is gamma, derivative is 
one2, over N squared for that's that. 

79
00:07:07,417 --> 00:07:11,969
And then the next term, third derivative, 
is 14. 

80
00:07:11,969 --> 00:07:16,414
over N fourth. 
So, that gives us the harmonic numbers 

81
00:07:16,414 --> 00:07:20,860
for Euler–Maclaurin summation to within O 
N1/4. 

82
00:07:20,860 --> 00:07:22,025
to the one fourth. 
So for N1,000,000, equals a million, 

83
00:07:22,025 --> 00:07:29,223
you're not going to see a deviation from 
that for 24 decimal places. 

84
00:07:29,223 --> 00:07:34,070
And the another classic example is 
Stirling approximation. 

85
00:07:34,070 --> 00:07:42,620
and again now [COUGH] [COUGH] a log of N 
factorial 

86
00:07:42,620 --> 00:07:48,570
that's the sum of K, so F of K is just K 
and so, 

87
00:07:48,570 --> 00:07:50,341
sorry. 
F of k is log k. 

88
00:07:50,341 --> 00:07:56,153
So its integral in computed out. 
and again, there's a big jump in 

89
00:07:56,153 --> 00:08:01,894
precision right at the end where the last 
term's big-oh of one over N cubed. 

90
00:08:01,894 --> 00:08:07,422
so that's going to be a very good, 
approximation, for, in the ranges of 

91
00:08:07,422 --> 00:08:11,320
interest. 
and we can use that for, other functions 

92
00:08:11,320 --> 00:08:14,793
as well. 
but these are the classics that arise 

93
00:08:14,793 --> 00:08:18,053
again and again in the analysis of 
algorithms. 

94
00:08:18,053 --> 00:08:21,810
And they're so useful because they're so 
accurate. 

95
00:08:21,810 --> 00:08:30,792
so here's a very example of applying the 
information that was talked about so far 

96
00:08:30,792 --> 00:08:36,164
in this lecture. 
so if we have Stirling's approximation 

97
00:08:36,164 --> 00:08:42,646
just take it over and over N. 
now what we want to do is use that to 

98
00:08:42,646 --> 00:08:49,271
figure out how 2N choose N rows. 
so we want to get two and choose N to 

99
00:08:49,271 --> 00:08:55,700
within big-oh of one over N. 
so that's a straightforward exercise 

100
00:08:55,700 --> 00:09:02,129
using the basic techniques that we've 
talked about with the algebraic 

101
00:09:02,129 --> 00:09:07,337
manipulations on asymptotic series let's 
look at how it goes. 

102
00:09:07,337 --> 00:09:13,929
and it's worth doing a couple of 
exercises of this nature and there are 

103
00:09:13,929 --> 00:09:20,031
plenty in the book because the. 
number of terms that arise that appear 

104
00:09:20,031 --> 00:09:26,360
daunting but you have the ability to wack 
them away with the big-oh and a lot of 

105
00:09:26,360 --> 00:09:29,619
them cancel out. 
so lets look at this. 

106
00:09:29,619 --> 00:09:36,020
So 2N choose N so that's 2N factorial 
over N factorial times N factorial so we 

107
00:09:36,020 --> 00:09:42,031
have complicated terms multiplied 
together we're going to use the explode 

108
00:09:42,031 --> 00:09:47,417
technique so that's equal to e to the log 
of 2n factorial minus two log N 

109
00:09:47,417 --> 00:09:51,164
factorial. 
So change multiplication and division 

110
00:09:51,164 --> 00:09:56,466
into sums of logs. 
okay so now those two functions we can 

111
00:09:56,466 --> 00:10:02,338
apply Stirling's approximation. 
So the next line is just plugging in, on 

112
00:10:02,338 --> 00:10:07,520
the first line is Durung's approximation 
for log of 2N factorial. 

113
00:10:07,520 --> 00:10:14,236
That's 2N, that log of 2N, 
minus 2N plus log of square of four Pi N 

114
00:10:14,236 --> 00:10:20,481
plus O of one over N. 
And the next line is subtracting off 

115
00:10:20,481 --> 00:10:29,242
twice again the formula for Stirling's 
approximation minus two and log N minus 

116
00:10:29,242 --> 00:10:35,863
plus log squared of two Pi N, not plus 
big-oh of one over N. 

117
00:10:35,863 --> 00:10:41,514
So that's 
the that's the quantity so now we just 

118
00:10:41,514 --> 00:10:47,159
have to do algebra. 
So in and you can see lot of things are 

119
00:10:47,159 --> 00:10:54,807
going to cancel out so say the first term 
on the first line is 2n natural log of 2N 

120
00:10:54,807 --> 00:10:59,724
The first term on the second line is 
minus 2N natural log N. 

121
00:10:59,724 --> 00:11:06,916
So that first one is log 2N is log N plus 
log two or its going to be left there as 

122
00:11:06,916 --> 00:11:10,650
2N Log two. 
then also look at the 

123
00:11:10,650 --> 00:11:14,990
[COUGH] what happens to the terms 
involving square root of Pi? 

124
00:11:14,990 --> 00:11:20,735
So, log a square root of four Pi N minus 
twice log square root of two Pi N. 

125
00:11:20,735 --> 00:11:27,075
If you just multiply that out there's a 
log two minus two square root of log two 

126
00:11:27,075 --> 00:11:34,119
the square root of then minus a log of 
square root of n so log two minus two log 

127
00:11:34,119 --> 00:11:40,458
square root of two, that's zero, so all 
that's left is minus log square root of 

128
00:11:40,458 --> 00:11:44,728
Pi N. 
so those two terms go to that one simpler 

129
00:11:44,728 --> 00:11:50,589
term [COUGH] and the 2N log two and 
that's all that's left. 

130
00:11:50,589 --> 00:11:54,640
The 2N cancels with minus two times minus 
N. 

131
00:11:54,640 --> 00:12:00,994
and so now, that's 2N choose N equals E 
to the 2N log two minus natural log of 

132
00:12:00,994 --> 00:12:05,908
square root of Pi N. 
Now, both of those terms have logs and 

133
00:12:05,908 --> 00:12:11,076
it's E to that power. 
So now we can undo the X blog technique. 

134
00:12:11,076 --> 00:12:17,176
the first term is four to the n. 
and the second term is, since it's minus 

135
00:12:17,176 --> 00:12:23,107
one over square root of Pi N. 
So that's an asymptotic expansion for 2N 

136
00:12:23,107 --> 00:12:26,930
choose N. 
two within one over N and again that's a 

137
00:12:26,930 --> 00:12:32,425
big number but if we need it to compute 
2N choose N over four to the N then we 

138
00:12:32,425 --> 00:12:35,903
get a function like one over square root 
of Pi N. 

139
00:12:35,903 --> 00:12:41,328
and that's going to be what we going to 
want to estimate the quantity of that 

140
00:12:41,328 --> 00:12:47,595
we're studying is as a typical example. 
So Stirling's approximation leads us to 

141
00:12:47,595 --> 00:12:53,785
good approximations of binomial 
coefficients using the x log technique. 

142
00:12:53,785 --> 00:13:00,560
so there we go one over four the n two 
inches in is one over square root Pi N. 

143
00:13:00,560 --> 00:13:08,256
okay so here's a, here's an application 
in the real world of this kind of 

144
00:13:08,256 --> 00:13:10,180
technique. 
so 

145
00:13:10,180 --> 00:13:17,290
the question is for some kind of 
computational process the data might be 

146
00:13:17,290 --> 00:13:24,317
represented as a binary tree with N 
internal nodes and the question is how do 

147
00:13:24,317 --> 00:13:30,990
you represent that, that binary tree? 
and you can think about different ways to 

148
00:13:30,990 --> 00:13:36,674
do it, but one thing that you can know is 
since there's one over N, the number of 

149
00:13:36,674 --> 00:13:42,359
trees is the catalan numbers, you have to 
distinguish among all the trees, so you 

150
00:13:42,359 --> 00:13:47,120
have to have at least log of that many 
bits in your representation. 

151
00:13:47,120 --> 00:13:53,659
otherwise the number of things, the 
number of things that you can represent 

152
00:13:53,659 --> 00:13:59,420
is less than two to the, that power and 
it's gotta be at least that big. 

153
00:13:59,420 --> 00:14:04,488
if you use fewer bits, then you can't 
possibly represent all the trees. 

154
00:14:04,488 --> 00:14:10,491
Now, someone who, didn't know esontotics, 
might respond, to the programmer, "That's 

155
00:14:10,491 --> 00:14:15,360
how many bits you need." But how's the 
programmer going to compute that value 

156
00:14:15,360 --> 00:14:20,562
for a million of a tree with a million 
nodes, it's, it's not concise, it's not a 

157
00:14:20,562 --> 00:14:25,631
value that's, easy to compute and all 
this is a well known function, maybe, 

158
00:14:25,631 --> 00:14:30,500
but, in general, faced with functions 
like that, that's not what we want. 

159
00:14:30,500 --> 00:14:38,935
but using the calculation that we just 
did, you can say that there's an extra 

160
00:14:38,935 --> 00:14:41,136
factor of N. 
[INAUDIBLE]. 

161
00:14:41,136 --> 00:14:45,354
It's four to the N over square to pie N 
cubed. 

162
00:14:45,354 --> 00:14:50,580
And if you take the log of that. 
log based two of that. 

163
00:14:50,580 --> 00:14:55,898
that's two N minus 1.5 log N. 
That's really close to 2N. 

164
00:14:55,898 --> 00:15:00,666
So need at least two N minus. 
So for 1,000,000 

165
00:15:00,666 --> 00:15:03,856
[COUGH]. 
you'd need, you know? 

166
00:15:03,856 --> 00:15:11,603
Two million - 1.5, natural log of, of log 
base two of a million, which is about 

167
00:15:11,603 --> 00:15:16,232
twenty. 
so you need two million - 30 bits, at 

168
00:15:16,232 --> 00:15:19,350
least. 
and that's an important. 

169
00:15:19,350 --> 00:15:26,662
practical fact to know actually there's a 
way to represent binary trees with two n 

170
00:15:26,662 --> 00:15:30,140
bits. 
So that's within 30 of the best that you 

171
00:15:30,140 --> 00:15:34,060
can do. 
and so people who are working with a 

172
00:15:34,060 --> 00:15:39,940
problem of this sort could stop there. 
I know at least 2,000,000 - 30 and I can 

173
00:15:39,940 --> 00:15:43,720
do it with 2,000,000 and I'm going to be 
happy with that. 

174
00:15:43,720 --> 00:15:48,232
in this is not the time to go through 
this in detail. 

175
00:15:48,232 --> 00:15:54,342
but the method of representing binary 
tree into in bits is to just do a pre 

176
00:15:54,342 --> 00:15:59,896
ordered traversal of the tree and write 
down zero every time you hit a internal 

177
00:15:59,896 --> 00:16:03,020
node, and one when you hit a external 
node. 

178
00:16:03,020 --> 00:16:08,227
and that's a unique representation of the 
tree that you can get back. 

179
00:16:08,227 --> 00:16:14,198
if you look in Algorithms fourth edition 
there's a code for doing that 

180
00:16:14,198 --> 00:16:17,791
representation. 
That's a F minus, fine example of why 

181
00:16:17,791 --> 00:16:22,496
asintotics are useful. 
Takes the functions that we get from 

182
00:16:22,496 --> 00:16:27,680
analysis and gives us a practical way to 
work with them. 

183
00:16:27,680 --> 00:16:34,620
[COUGH] so that's an introduction to 
asymptotic on finite sums.