Next to finish off our study of recurrence relations, we'll talk about the master theorem for divide and conquer recurrences. This is very important in the theory of algorithms. It's all about divide and conquer algorithms. So many algorithms gain their efficiency by attacking a problem of size and with the following steps. First divide it into smaller parts, so in the case of mergesword it was divided into two parts of size n over 2. More generally it might be parts of maybe different size. So we'll pick effect or beta, so it could be n over 3 or n over 4, whatever. And not only that, it might not add up to n. So there might be multiple parts, and say three parts of size n over 2 or 7 parts of size n over 8. Or whatever, so we'll parameterize both the number of parts and the size of each part. Usually, they try to do equal size. If you don't have equal size, then you have even more complications. So that's the first thing, divide into alpha parts of size n over beta. And then solve recursively, and then put the solution together somehow 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 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 what's called the master theorem that we'll talk about next. So first, here's some examples. So we did merge sort. For merge sort, problem sizes N/2, so that's beta 2. Two problems in size N/2, so that's alpha is 2. And the extra cost is N, so there's no log n. So delta equals 0, gamma equals 1. So that's .mergesort. 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 batchers is like mergesort, except the extra cost has a login factor. So this delta equals 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 2. 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 first cut at the analysis. A famous algorithm that got people interested in this, was multiplication. At the beginning, people were wondering how difficult is the problem of multiplying two n-bit integers. And it seemed like the best you could do would be the grade school method of multiplying two n-bit integers by taking each bit, multiplying by the all the other bits, moving over one, and then adding up the little n-by-n table of bits. That's going to take time proportional to n squared. And then the Karatsuba multiplication algorithm came along, where they showed how to multiply input integers, by dividing into three problems, of size n over 2. 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, however though. Seeing the matrix multiplication algorithm, where you have two N by N matrices that you want to multiply together to get the N by N result. Seeing 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 entries in the result, which would be n cubed. But Strassen showed that you could solve it with a divide and conquer algorithm where you divide into seven problems of size N/2, and then get the final solution with an extra N. So it was an algorithm that did matrix multiplication in a number of operations described by this recurrence. So these are three examples of divide and conquer algorithms that all have the same general character. And so with the master theorem, it says that it gives a, under the supposition that you have a problem besides alpha parts of size n over beta with extra cross omicron n to the gamma log n to the delta that's going to lead to a reoccurrence. And the reoccurrence is going to look a lot like our merge sort reoccurrence, except instead of the floors and ceilings, we add little tiny constants to each one of the problem part sizes. N over 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 to throw out a few terms. So, as general as we can do is to get alpha terms of the form N over beta plus O of 1 and then we add on the extra 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 cross term and the log to the base beta of alpha or alpha's the number of parts and beta is the amount, the fraction that you divide n by. So and 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 n. And it's n to that power. And so here's in the book is a little graphic way seeing how these three cases have to be different. So this is the case that alpha equals 3. So we have three parts and so it has to do with the relationship our number of parts and the size of each part. And the one in the middle is like what we did with mergesort. If you have three parts of size N over 3, then the total number of problems that you analyze in every case, the size of them is going to add up to N at every stage. It's just that you divide by 3 every time. And then every time you divide by beta you keep going until you get to 1, so that is the log beta of n, this should say n, not alpha. And so that gets you down to a problem size of with log and steps you get down to problem size of 1. 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. So here's the typical applications. So, This is for mergesort, you get N log N, for Batcher's network you get the extra factor of log N. For Karatsuba multiplication you get best case here, so it's N to the log base 2 of 3 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 idea of the Master Theorem is that it give us good asymptotic growth rates. And very important for the theory of algorithms to help us understand what we can do in terms of asymptotic growth rates. Now, there's a lot of versions that have been studied about the Master Theorem. There's some cases where you can get precise results like we did for mergesort, 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, you can 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 Drmota that actually captures in general, all the kinds of oscillations as we determine for mergesort. Now really appreciating how and why the solution works in the way that it does is going to be something that's going to require everything that we cover in analytic combinatorics, including part two. But people will have some idea for how the mathematics manages to model what actually happens in the computer algorithm, and this is really an important contribution of analytic combinatorics in this case. So that's the Master theorem for studying divide and conquer algorithms. And that'll complete our study of recurrence relations. Next time we'll move on to generative 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. First one is Exercise 2.17. There's a particular data structure called a 2-3 tree. That 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, problem is to go ahead and solve this recurrence. And it's an interesting random process. And leads to interesting occurrence that's got a solution that's definitely a practical interest. [COUGH] Here's another one is to go ahead and try divide by three and conquer. So a sub n equals 3, A over 3 plus n. So maybe mergesort by dividing into three parts and then doing a three way merge. So what is the periodicity in that thing look like? So again, using the same methodology that I use for divide by two, do this one and try to discover 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 set up standard draw or come up with your own way to plot the values of sequences. And then go ahead and do that exercise for plotting. Divide by three and conquer. I think doing that work will help you make sure that you understand the material that we've done so far and set you up for the next lecture.
