Next, to finish off our study of 
recurrence relations, we'll talk about 
the master theorem for divide and conquer 
recurrences. 
and this is very important in the theory 
of algorithms. 
And it's all about. 
Divide and conquer algorithms. 
So many algorithms gained their 
efficiency by attacking a problem of size 
n by, with the following steps. 
first divide it into smaller parts. 
So, in the case of merge sorter was 
divided into two parts of size n/2. 
more generally it might be 
parts of maybe different size. 
So we'll pick a factor beta, so it could 
be n over three or n over four, whatever. 
and. 
Not only that, it might not add up to n. 
So, there might be multiple parts, say 
three parts of size n/2 or seven parts of 
size n/8, or whatever. 
So, parametrize both the number of parts 
and the size of each part. 
Usually they try to do equal sizes, if 
you don't have equal sizes then you have 
even more complications. 
so that's the first thing, divide into 
alpha parts of size n/beta. 
And then solve recursively 
and then put the solution together some 
how with extra cost that is described by 
a standard function. 
and in the theory of algorithms remember 
we don't care about the constant, we just 
want to get the order of growth. 
so, we'll say theta of N to the gamma log 
N to the delta. 
So there's a lot of problems that fall, 
within, this paradigm. 
and again, it's easy to write computer 
programs that have this kind of behavior. 
Just write a recursive program that does 
the things. 
And so, for the theory of algorithms, for 
decades, people have been developing 
computer programs that. 
that. 
Are gain their efficiency by this 
strategy and what we want is to analyze 
them. 
So very early on people started studying, 
general models for computer programs like 
this and that's why, what's called the 
master theorem that we'll talk about 
next. 
So, first, here's some examples. 
So, we did merge sort. 
So for merge sort problem size is n/2 so 
that's beta two. 
two problems of size n/2 two, so that's 
alpha is two. 
and the extra cost is n, so there's no 
log n so delta equals zero, gamma equals 
one. 
So that's merge sort. 
here's another example that's similar, 
So that's Batcher's network for, sorting. 
so that's a different approach to, 
sorting. 
Where we don't do it with programs, but 
we do it with hardware. 
and Batcher's is like Merge Sort, except 
the extra cost has a log n factor. 
So this delta1. 
= 1, that's batcher's network. 
So, now I'm going to only write the ones 
that are valid when N is the power of 
two, taking into account the floors and 
ceilings that are needed for, general N. 
takes us, to another level, that we don't 
necessarily need to worry about, in many 
cases, with the theory of algorithms. 
and so, we'll try not to worry about that 
in this cut at the analysis. 
a famous algorithm that got people 
interested in this was multiplication at 
the beginning people were wondering how. 
[COUGH]. 
Difficult is the problem of multiplying 
two N bit integers. 
It seemed like the best you could do 
would be the grade school method of 
multiplying two N bit integers by taking 
each bit multiply by all the other bits, 
moving over one and then adding up. 
Little N by N table of bits that's going 
to take time proportional to N squared. 
and then the suitable multiplication 
algorithm came along where they showed 
how to multiply input integers by 
dividing into three problems of sizing 
over two. 
and then combining with an extra cost of 
N and so that's the number of steps 
required for that particular 
multiplication algorithm. 
And a related one that's also very famous 
is the Strassen Matrix Multiplication 
Algorithm. 
it seemed that matrix multiplication 
algorithm where you have two N by N 
matrices that you want to multiply 
together to get an N by N result. 
it seemed that for every entry in the 
result you needed to have a dot product 
of a row and a column. 
which is going to require N 
multiplications for each of the n squared 
entry's in the result which would be n 
cubed and but Strassen showed you could 
solve it with a divide and conquer 
algorithm where you divide into seven 
problems besides n/2 and then get the 
final solution with extra N, so, it's an 
algortithm that did metric 
smallification, and a number of 
operations discredit by this reccurence, 
so these are three example of divide and 
conquer algorithms that, all have the 
same general character, and so what the 
master theorm says, is that, it, that 
gives, a, under the supposition that you 
have a problem. 
Size, alpha parts of size n over beta 
with an extra crossed n to the gamma log 
n to the delta, that that's going to lead 
to a recurrence. 
And the recurrence is going to look a lot 
like our merge sort recurrence. 
Except instead of the floors and 
ceilings, we add little tiny constants to 
each one of the problem part sizes. 
because n/beta, when, it has to be an 
integer, so you have to have some floors 
and ceilings in there somewhere or maybe 
the problem size is throw out a few 
terms. 
So, as general as we can do is to get 
alpha terms of the form n/beta+O(1), + 
O(1) and then we add on the X, 
cost, and the master theorem, gives the 
order of growth of the solution. 
and it all has to do with the 
relationship between this extra power 
gamma in the extra cost term and the log 
to the base beta of alpha were alpha is 
the number of part, parts in beta is the 
amount the, the fraction that you divide 
n by. 
so, in what the solution is, is three 
different cases if gamma is small 
compared to log beta of alpha. 
It's n to the gamma log n to the delta. 
if it's equal then there's an extra 
factor of log n. 
and then if gamma is big, so that means 
the extra cost is big. 
Then that's going to dominate. 
and it's n to that power. 
and so, here's a 
In, in the book, it's a little graphic 
way of seeing how these three cases have 
to be different. 
so this is the case that alpha = 3 so we 
have three parts. 
and so it has to do with the relationship 
between our number of parts. 
and the size of each part. 
And the one in the middle is like what we 
did with merge sort. 
If you have three parts of size n over 
three. 
Then the total number of problems that 
you analyze at every case. 
The size of them is going to about add up 
to n at every stage. 
As you see, you divide by three every 
time. 
And then every time you divide by beta, 
you keep going until you get to one. 
So that's the logbeta(n)). 
beta of n, this should say, n at alpha. 
So that gets you down to a problem size 
of with log N steps. you get down to the 
problem size of one, so that's where you 
get the extra log N factor. 
if on the other hand you're dividing into 
so three parts but they're small then 
what's going to happen is that really all 
that matters is the first cost. 
And the rest of them become not so 
significant. 
So, really, the cost of doing it the 
first time is what counts. 
but if your problem sizes are bigger, 
then it's all about the number of 
problems that you get at the end. 
and that's what, n to the log beta of 
alpha comes up. 
So that's the master theorem for Divide 
and Conquer algorithms. 
and, so here's the typical applications, 
so, 
This is for mergesort you get n log n for 
batchers network you get the extra factor 
of log n. 
for karatsuba multiplication you get this 
case here so it's n to the log base two 
of three. 
which is about 1.585 not N squared. 
it's less than N squared and for Strassen 
you get N to the 2.8, it's less than N 
cubed so 
the basic ideal of a master theorm is 
that it gives us good asontotic growth 
rates, as very important for the theory 
of algorithms to help us understand the 
what, we can do in terms of asontotic 
growth rates. 
now there's a lot of versions, that have 
been study, about the master theorm 
there's some cases where you can get 
precise results, like, like we did for 
merge sort. 
and for the most important algorithms 
that people use in practice, and we want 
to predict performance and compare 
algorithms, we have no choice but to go 
there. 
the more general results in the theory of 
algorithms and go even more general than 
where we went in terms of the extra cost 
of doing the combination and those are 
certainly available. 
and then actually very recently a full 
solution, using analytic combinatorics 
was developed by Szpankowski and Dramoda 
that actually captures in general all the 
kinds of oscilations as we determine for 
merge sort. 
Now really appreciating how and why this 
solution works in the way that it does, 
is going be something that's, going to 
require everything that we cover, in the 
analytic commitorics, including part two, 
but people will have some ideal for how 
the mathematics manages to model what 
actually happens in the computer 
algorithm and this is really an important 
contribution of analytic commitorics in 
this case. 
So that's the master theorem for studying 
divide and conquer algorithms and that 
will complete our study of recurrence 
relations. 
Next time I will move on to generating 
functions. 
So here are a few exercises that would be 
worthwhile for you to take a look at to 
cement your understanding of this 
material in order to be ready for the 
next lecture. 
the first one is exercise 2.17. 
there's a particular data structure 
called a two three tree. 
it doesn't matter too much now what it 
is. 
but there was a paper by Yao that proved 
that a certain property of this tree. 
which is described here is described by 
this second order first order recurrence. 
and so it's a complicated first order 
recurrence. 
And so the, the problem is to go ahead 
and solve this recurrence. 
And it's an interesting random process 
and it leads to interesting recurrence 
that's got a solution that's definitely 
of practical interesting. 
[COUGH] here's another one, is to go 
ahead and try divide by three and 
conquer. 
so a sub n = 3 A of floor event over 
three + N. 
So maybe merge sort, by dividing into 
three parts and then doing a three way 
merge. 
and so what is the periodicity in that 
thing look like? 
so again using the same methodology that 
I used for divide by two do this one and 
try to discover the, the interesting 
performance behavior of something like 
this and think about how we might compare 
two algorithms like that. 
now in order to address those you're 
going to again, want to read the chapter 
on recurrences in the book. 
and write up the solution to the 2-3 
trees exercise. 
And then, set up standard draw or come up 
with your own way to plot the value of 
sequences. 
and then go ahead and do, that exercise 
for, plotting divide by three and 
conquer. 
I think doing that work well help you, 
make sure that you understand the 
material that we've done so far and set 
you up for the next lecture.