Next we're going to talk about an 
intricate extension of the asymptotic 
techniques that we're looking at, where 
there's two variables involved. 
And these arise frequently in the 
analysis of algorithms. 
So. 
In a lot of times in the study of 
algorithms we have two variables that we 
are working with. 
One is the size of the problem and the 
other is the cost. 
so we're going to wind up with intricate 
expressions that are involved with those 
two variables and they might vary 
independently. 
So, we have some definite challenges. 
The problem is as I indicated when 
talking about doing sums is that, the 
relative values of the variables, might 
matter. 
and that makes it even more challenging 
to, deal with sums over the whole range 
of relative values. 
and you'll see what this means when I get 
to some applications. 
fortunately as was the case with the 
harmonic numbers and sterling numbers 
where, there's a couple of fundamental 
functions that, arise over and over again 
that take most of the work. 
similar is true of functions of two 
variables. 
There's a couple of fundamental functions 
that arise. 
and we'll look at the aymptotics of 
those. 
and they are, are the ones that arise 
most often. 
And if it's not that function it's a 
function that similar that we can model 
the analysis on the analysis that have 
developed, been developed classically for 
these functions. 
so first example is the binomial 
distribution. 
again that's okay. 
Might be related to the cost, and might 
be related to the problem size how are we 
going to compute values like that for 
[COUGH] 
how are we going to make computations if 
we wind up with an expression like that. 
It turns out that as I just explained for 
the, Catalan numbers. 
If k is zero, that's close to, one over 
square root of pi n. 
That's two entries in. 
but If k is large, that's exponentially 
small. 
It's a very, very tiny quantity. 
So we're going to have to come up with an 
analysis that tells us, both those 
things. 
another example is called the Ramanuj-, 
Ramanujan Q distribution. 
It's actually kind of similar. 
A binomial coefficient is n factorial 
over n- k factorial, k factorial. 
this one's n minus n factorial over n- k 
factorial, n to the k. 
And that actually arises in the analysis 
of several classical, algorithms. 
in that one, if K=zero. 
It's just infectorial, or infectorial. 
It's one 
And, but if K is close to N that one is 
exponentially smaller. 
N to the N is way smaller than N 
factorial. 
So this the types of functions and the 
types of challenges that we face with 
analyzing functions of two variables. 
now to get an idea of, of, what goes on 
we use plots like this where we draw one 
line for each value of k and then we 
scale you can't, in a graph, you can't 
have a variable n. 
So we make that a variable n by scaling 
the actual values by a factor of, of 2n. 
so the binomial coefficients 
so [COUGH] for k2. 
= 2 it's, one quarter, one-half 
one-fourth. 
then 
Or, just forgetting about the, [COUGH]. 
The exponential scaling factor that's 
121. 
And this is 1331. 
14641, so you can see Pascal's Triangle 
in these plots. 
And what happens, as many people are 
familiar, is that as n increases this 
discrete two variable distribution 
converges to the normal distribution. 
and to and to a curve that we can 
describe with a simple mathematical 
function and we're going to see the math 
to get us to the place that this picture 
shows us. 
we ought to be able to have a simple 
description of this distribution and we 
do. 
this is what Ramanujan Q distribution 
looks like. 
Again the same type of plot for different 
factors of K we draw a curve. 
so k goes from zero to n. 
when k is small it's very close to one. 
when K gets close to N over two, it 
becomes extremely small and then there's 
a curve that describe its growth so for a 
large N we ought to be able to use some 
function that defines that curve for any 
value of K and that's what we're after 
with bivariate asymptotics. 
now 
let's take a look, first, at the 
Ramanujan Q distribution. 
The calculation's a little bit simpler. 
It's an extension of the calculation that 
we did for the catalyn numbers. 
it's just that now, we're carrying on 
this variable k. 
So, first step is use the x log 
technique. 
N factorial where as k factorial to n to 
the k is e to log of n factorial - log of 
N - K factorial - log of N to the K, 
which is K log N. 
So that's the first step. 
Now, how are we going to expand each one 
of those? 
Well, the first two, is, are just, 
handled with, Sterling. 
so we'll use, Sterling's approximation to 
log n factorial. 
and just plug that in, in both of these 
cases. 
so that says log n factorial is n + 
one-half log n - n + log of square root 
of two pi + O of one over n. 
Now the difference is that's what we use 
for the first term, for the next term we 
have that value of k that we have to 
worry about so we're going to have O of 
one over N minus K, which we can cover 
with O of one over N. 
So that's plugging in Sterling's formula 
for the first two terms and then there's 
the - K log N term still left there from 
the N to the K. 
So again, we've got a bunch of terms. 
Three terms for the log N factorial, 
three, three terms for the log N minus K 
factorial, and then the minus K log N. 
And we've got to do algebra to deal with 
those terms. 
And again, there's some cancellations 
that are going to help us out. 
Log square to two pi cancels the minus N 
plus N cancels 
There's 
log of n - k is log of n+ log of 1-k over 
n. 
so we get some cancellations there. 
so 
if we collect all those terms, with all 
the cancellations. 
that's, what we're left with e to the -n 
- k + one-half log of 1 - k over n. 
You might want to check, the math on 
that. 
But, it's all, simple algebra that leaves 
us with that. 
And the only technique used is log of n - 
k equals log N plus log of one minus K 
over N, and we're down to just a few 
terms. 
[COUGH] so. 
Now we have to expand the log of one 
minus K over N and that's minus K over N 
minus K squared over 2N squared, plus all 
of K cubed over N cubed, so now we're 
carrying both variables in the big o 
term, which can be a little tricky, we're 
tryin to, make this work for as many 
values of K as we can, but different 
values of K, particularly when K is 
proportional to N, are going to give us 
different asymptotic accuracey, and 
that's one of the challenges with 
vivariant asymptotics, but we'll. 
Carry it in this form and see where we 
go. 
So just plugging in that formula and 
doing the math. 
is so there's a minus K over N, we're 
multiplying by N. 
And again, you can go ahead and do the 
math. 
not too much survives. 
there's K squared over two N minus K 
squared over N so that's minus K squared 
over two N. 
The K is canceled so all we get is even 
minus K squared over two N in the end. 
And then what's left over are the two 
error terms and those error terms are 
just doing the math. 
If you multiply N times. 
A of k cubed over over [INAUDIBLE] k 
cubed over n cubed you get k cubed over n 
squared and if you multiply k times sorry 
and then what's left is the O(k)/n. 
So those are valid formulas, but the 
interpretation of the formulas going to 
depend on the value of k. 
And it tells us a lot. 
For a small k, for a relatively small k, 
it says that it's going to close to 
e(-k^2/2*n). 
to the - K^2 / 2N. 
That's the curve that we see when so if 
we just, analyze, that there different 
values, if this, in fact if K is like N 
to the two fifths say, which is a pretty 
good sized value, then, K over N is going 
to be one over N into three fifths K 
cubed or ran squares one over into the 
four fifths, so that's the, error term, 
seems like we're shaving into, tiny 
dinstinctions but, the main point is one 
over into, positive power, that's going 
to be a big, 
A big distinction when K is square root 
of n they are about the same. 
Now k gets bigger and this term starts to 
starts to pick up but we can work with 
others different ranges and really the 
main point of this derivation is to show 
that for most of the curve, remember the 
plot showed up to square root of n its 
got a fine curve when description of that 
curve we have it its e to the -k squared 
over 2n. 
which is a simple function to work with 
as opposed to the original 
description involving factorials. 
a similar situation works for the 
binomial distribution. 
and again, this is just an exercise. 
using Sterling's formula, carrying 
through all the air terms and making sure 
that you get their cancellations. 
and its definitely worthwhile to close 
the book, turn off the computer and try 
to do this derivation, just as an 
exercise in Algebra perhaps, because you 
can see when you do that, how the 
cancellations happen and simplify the 
calculations. 
And, everybody who works in the That sort 
of field knows that, if you do a long 
calculation like this and you miss a 
term, you're going to get, something very 
exciting at the end, that, maybe, is, not 
relevant, or wrong simply by missing a 
term, because, you're, E to a power, high 
and you accidenttaly forget, to cancle 
out a an N term you get E to the enth, 
which is, probably is not there at all. 
ust as an example. 
So we'll do the calculations. 
I'm not going to explain every term on, 
on these calculations, but because 
they're actually very similar to the ones 
that we just did. 
You apply Sterling's Formula. 
and so that gives three lines, each with 
four terms, one for, each of the main 
term. 
and again, initially, we can just use 
O(1/n) for the whole range, where we 
start to have to carry terms that involve 
O(k/n) is, when we expand log n-k to be 
log n + log of 1 - K / N. 
And log of N plus K to be log of N plus 
log of one plus K over N. 
that's K over N's are 1's in those 
asymptotic series are the ones that give 
us some complication. 
so when we do this and do the algebra. 
the a bunch of things cancel. 
The two N cancels with the two Ns and so 
forth. 
and so these are the terms that survive. 
and again that's pretty much straight 
forward algebra with the additional 
proviso that we're doing that expansion 
log. 
N minus K equals log N plus log one minus 
K over N. 
The terms of [INAUDIBLE] most of them go. 
and so we're left with that. 
And then these two terms are kind of 
similar ones got a - K ones got a + K and 
just rearranging terms in terms of K x 
this difference. 
Of log(1-k/n), log(1+k/n), and 
(n+1/2)*(the sum). 
Those two, that sum and that difference, 
that's one of the first exercises that we 
did. 
And those things collapsed down to just 
one asymptotic term. 
so the sum of them is asymptotic to minus 
k squared over n squared. 
And the difference of them is asymptotic 
to minus two over n with again, big O 
terms involving k cubed. 
so substituting that in. 
gives us, 
E to the two N log two, minus natural log 
of square root of pi N, that's, the only 
of pi that's left over from all the math, 
minus K squared over N of plus, the big 
ol turn, and then just undoing the act 
log technique, 
E to the two n log two, that's four to 
the n. 
E to the minus log squared of pi n, 
that's one over square root of pi n. 
And then what's left is e to the minus k 
squared of n. 
So [COUGH]. 
One over 4n, 2n choose n minus k is e to 
the minus k squared over n over square 
root of pi n. 
And that's the normal approximation to 
the binomial distribution. 
and that's accurate for a broad range of 
values of k it's only, for this 
approximation. 
It's only when k gets bigger than N to 
the three-fourths that you know, the 
approximation doesn't work And again, 
remembering from the curves when k is 
that big we can use independent means to 
prove that the terms are very, very 
small. 
so there's certainly a lot of math on 
this slide. 
on the other hand the bottom line is a 
fundamental, classical resolve in 
mathematics. 
And the techniques used, 
what makes it complicated is really just 
elementary algebra. 
so it's an exercises in doing elementary 
algebra well. 
and it's interesting these kinds of 
calculations still nowadays most people 
do them by hand because it's difficult to 
have automatic calculations carry through 
on the bivariate to the extent that we'd 
like say. 
so a lot, lots of people still do these 
kinds of calculations by hand. 
And there is plenty of other examples in 
examples in the book and so I'm not going 
to go throw all those examples again. 
These functions arise, very often and we 
can go back to a table like this to get 
the approximations that we need later on 
when we encounter these functions in 
applications. 
so. 
again different arguments depending on 
different ranges of K in most cases will 
have a. 
[COUGH] An approximation that's true no 
matter what the value of k is, and then 
other times we'll have a more refined 
approximation that'll give us a, a little 
more accuray for near the center. 
So, that's the end result for the normal 
distribution, then there's the so called 
Pawson distribution, which I haven't 
talked about very much, but which falls 
to the very same kinds of techniques and 
I'll talk about it when we come to it in 
the context of applications. 
And again if you look at the derivation 
in the book or you can just, deal with 
that by using the X blog trick, a lot of 
things cancel and the end result is a 
famous result that for. 
[COUGH] 
nth of the that n choose k times that 
binomial for probability that's kind of 
small chance of occurring this lambda to 
the KE - lambda over KE factorial and 
we'll talk about applications of that 
later over. 
Now just in terms of the math its 
She should appreciate that, the very same 
techniques that we did on one slide will 
give this kind of approximation, these 
kinds of approximations. 
in the Q distribution that I talked about 
E to the minus K squared over N. 
to within one over square root of N 
uniform or more accurately, near the 
center, those are the kinds of bivariat 
approximations, that we can develop and 
they're extremely, important in, not just 
analysis of algorithms, but in many 
applications, it, it's far easier to work 
with the standard mathematical functions, 
like E to the minus K squared over N, 
then it is to, work with the factorial 
representations, which are exact but 
carry a lot of information that make 
calculations difficult. 
so, 
Most of the time, we'll be coming back to 
this table. 
and picking out these kinds of 
approximations when these sorts of 
functions arise in the analysis of 
algorithms. 
And we have similar functions that arise. 
we'll go back to the derivations. 
And see that they can be handled with the 
same basic method. 
Really, the ex-blog technique plus 
application to Sterling's formula So the, 
the next challenge that we're going to 
have now is though what do we have when 
we have a sum that involves one of these 
functions? 
and so the example that we'll do is the 
so-called Ramanujan Q function and that's 
a critically important function in the 
analysis of algorithms so. 
It's the Ramanujan distribution summed 
over all values of k and it's basically 
asking what's the area under the curve. 
and the challenge is that we're going to 
need again it's nearly one for small K 
and it's negligible for large K. 
So we're going to need to use different 
approximations and different parts of the 
range to get the answer. 
This is a very typical situation so 
that's why we need bivariate asymptotics. 
to make sure that we can have good 
estimates in the whole range that we can 
use to estimate the sum. 
the general method there is referred to 
as the laplace method. 
If you have to approximate a sum and this 
is just a, schematic representation of 
the situation. 
what usually winds up being effective is 
the tails are going to be small so we 
will restrict the range to an area that 
has what counts and then 
Find an approximation that works there 
and then 
What we can do is, 
Extend the range, so rather than, the, 
the point is that, that approximation 
usually is also going to be very small on 
the tails, so we can just extend the 
range back out. 
So we take out the original tails we put 
in the approximation, we use the, both of 
them are exponentially small, by 
comparison with the value of the whole 
sum, so it doesn't matter which one that 
we use. 
and then that gives us a way to get a 
concise approximation of the whole sum. 
That's called the Laplace Method and then 
usually one of the advantages of 
converting from a representation 
involving factorials to a representation 
like e^(-k^2/n) is that we can use an 
integral. 
For functions like that. 
And then you use that approximation to 
get the answer. 
Where integral with discrete doesn't do 
the job for us, usually. 
So let's look at how this method works 
for the Q function. 
And, and it's actually very 
straightforward. 
So what we're going to do is just pick a, 
a value. 
K0 and split into two parts for values 
less than K0 and values bigger than K0. 
You remember for small Ks where it's 
significant for large K it's going to be 
negligible. 
and going from the u, 
[COUGH] approximations that we developed 
before, for example, if you take K zero 
to be like N to the two-thirds and then 
the tail is going to be exponentially 
small, and I won't do the detail of that. 
And then for the tail's exponentially 
small, and not only that. 
We have a good approximation of the sum, 
and for k<k0. 
For all of those values, it's not far 
from E(-k^2/2*n). 
to the K^2 / 2N. 
That's the approximation that we just 
developed. 
Very close to that, actually. 
so then we can, now we can just, but that 
one also for large k is going to be 
exponentially small, so we might as well 
just extend the range back to be an 
infinite sum. 
because the tail is also exponentially 
small for that one. 
And now that sum, we can just approximate 
with an integral. 
And if you do that, you get square root 
of pi, N / 2. 
So, and again that's the true value of 
doing asymptotic calculations. 
This function, q(n), well it's a precise 
description of some mathematical quantity 
that's going to be really difficult to 
compute. 
But if you know the sqrt(pi*n/2), then 
that's something that you can work with. 
And we'll be coming back to applications 
that use this function later on. 
that's an introduction to bivariate 
asymptotics. 
Now I want to finish up by giving a few 
exercises that how you might do, before 
the next lecture to test your 
understanding of asymptotics. 
so the first one has to do with, where I 
started with, is how small is, 
exponentially small. 
And this is just trying for a couple of 
values of Alpha and Beta comparing with 
the values of Alpha to the n and Beta to 
the n. 
And, really showing that Alpha to the n 
is, the larger ones is going to be really 
good [COUGH] approximation. 
So here's another one an opportunity to 
go through those calculations that I did 
at the in the last section. 
there's another Ramanujan function 
actually there's three famous ones but 
this is another called the p function 
it's also the r function which is 
discussed in the book. 
and that's 
this function, sum over K, of N minus K 
to the K, N minus K factorial run 
factorial, that one also, is approximated 
by square root of pi N over two. 
And you're going through the tech, the 
steps that I did for the Q function, for 
this function, will be a very instructive 
if you want to test your understanding of 
this material. 
[COUGH] so those are 
So, so, one thing that you might do just 
to get started is write a program that'll 
print. 
log base two of n [INAUDIBLE] k. 
and just use what we've talked about in 
this lecture. 
get that done. 
That's an intersting excercise. 
and write up solutions to the two 
exercises that I just gave. 
and again if you're not comfortable with, 
with using text tech, either on paper or 
with Math jackson HTML. 
That'll certainly provide some practice 
or I'll write it up by hand I don't write 
stuff up by hand anymore, but some people 
do. 
and then read the chapter on asymptotics 
in the text for much more detail on all 
the information we've covered. 
in the next lecture we'll put together 
all the things that we've talked about in 
the previous lectures. 
And see how they fit together to form the 
basics of analytic combinatorics. 
then we can then go on to apply to the 
analysis of algorithms.