Video 5-2: The Master Theorem
CS 566 – Efficient Algorithms (Winter 2026-27) · unit page
· YouTube
2026-11-10, 34:43
The transcript was generated automatically by YouTube's speech recognition and is offered as is. It may contain errors, in particular in concerning technical terms, names and formulas.
0:04 Where we left things was with the master theorem. Recurrences of specifically this type that I have a a recursive calls for smaller subpros and the sub problems are by a factor b smaller and then I pay some overhead for uh the conquer step if you like. And um for many typical cases the master theorem gives you a shortcut to directly tell you what the final um running time of this is. Uh well the running time is this one. It gives you a theta class not the constant. And uh which of these cases applies depends on how this function f the conquer cost relates to u the ratio of of subpros sizes and number. We've done an example last time. Um let me before we continue uh with a bit the algebraic approach try to illustrate um why these three cases in the master theorem arise. Okay. And for that I I want to just essentially assume you insert into the recursion again and again. So what you see here is for a typical recursion here the parameters A, B and D you can play with. The important part is this is the recursion and you may recognize this is essentially something like merge sort.
1:28 Um I have uh two recursive calls to sub problems of about half the number of elements and I have linear effort to do that. Um if you wanted we can make it the element visits like this right we had a factor two here if we were strict and then the d was even zero but um this doesn't make a big difference let me make for the nicer picture let me keep d at one now what what happens here is if I start with just the leaves then the whole contribution comes from this last call of size zero and uh as If you um increase the input size, what you see here is is essentially the input size or up here it is. This is the topmost is the f cost. This additional conquer cost for the topmost recursive call. Then we have two recursive calls for half of the size and each of them contributes f of n half which here as the picture shows adds up to the same as the first recursive call.
2:37 Of course you know this that's how it is in merge sort. We uh split the number of elements in half but then we also have linear costs in each of the sub problems. So if you sum that up you have a cost of roughly n across every level. So there's nothing new here. If you keep going like this you see that the the sub problems become smaller and smaller. But what doesn't sh change is the shape of this overall figure. And as you zoom out more and more, what you get is is one large uh rectangle. It's as wide as f of n, the initial kind of cost of the topmost call. And it's as tall as well, as long as we have to recurse. And we'll work that out in in the algebra part how tall that is. If you said n to infinity, then it's also infinite. But it basically comes from how often do you have to divide by two before you're at n or it'll be log base 2 of n. Right?
3:42 Okay, that's one option how this can pan out. And this is the second case of the master theorem where we know this login is the height of this rectangle and the uh c to the n to the c where c here is just one uh that is the the width of the rectangle.
4:03 Now if you play with this a bit and say we have um instead now say three recursive calls of the same size and we don't change anything else. What should happen? Well, I uh should get wider and wider at the bottom because with each recursive call I'm creating more effort than I'm I'm uh making the problem smaller. So if if you run that, you'll see precisely that it starts out the the lowest level with the leaves is slightly smaller because I have a factor one and here a factor two. But the level above is always the one that uh grows and grows. And you see again there's a certain convergence to a limit shape and you'll see that when it speeds it up. Now that limit shape is actually just a a flat line at the bottom. There's nothing left in terms of the height. you do these recursive calls but in the limit the whole contribution is dominated from the last few levels and that's when you have this first case here um what essentially dominates is the number of leaves the width at the bottom is all that counts again for our recurrence here this would be would be a well C is now this log base log base 2 of three 1.58 85. That's the number of leaves you get if you start out with n.
5:27 Not a very uh pleasant number. If you want a more pleasant number, you could turn this to four. Then maybe uh the picture is essentially the same. But here c would be just two. So that overall result is n squ. Right? That's the first case of the master theorem. The last case you get is if you divide the problem up into more pieces into smaller pieces but relative to the reduction in size the pieces are few. For example, if you have two recursive calls on a third of the input. Okay. Then um if you uh apply the same here you see that the most expensive part is always the first call because you spend linear time up here and that remains the same. All that you do in the further recursive calls is less effort for quite a while. It seems like this is not that much smaller than the top. But again in the limit you see everything vanishes to just one line at the top. So you have these these three extreme regimes. It can be perfectly balanced or everything is dominated by the lower level or by the first level.
6:40 And here at this top level, that's why you need these annoying regularity conditions because now everything is dominated by the first call. And if that function f does annoying things like jump around peacewise defined functions or so on, um you get into trouble with this statement of of theta f of n. But that's really all there is going on. The dominant contribution here just comes from the first level.
7:13 Uh if the pictures don't convince you, they really should only give you an idea. They shouldn't convince you, but uh maybe they guide what comes. Question.
7:27 Uh we'll do that on examples. You'll see this is the easy part usually. uh you'll see examples and maybe then um we can talk about it again. Uh for now let's assume the recurrence is just given right it's uh falls from the sky and um many examples to come and maybe it looks in general like this and uh you can do what the animation showed for specific numbers of a and b you can do that in in general by just inserting it symbolically. So if we start with our recurrence and we assume n is large enough. I can insert here again what the recursive definition is. So the recursive definition is a times the same argument divided by another b and I have to add the f of n which is here f of n divided b. Right? The old this one just stays. This one just stays. Now for this one I can again insert the recursive definition. So I can keep doing this and then um you can maybe spot the pattern. What happens?
8:28 You keep inserting here and making n smaller by a factor b each eventually you reach some say one you reach some boundary value. I'm assuming that n is a power of b here. So after k steps where k is is log base b of n I'm reaching this this uh boundary condition and I have collected as many a's uh up front uh before the t as I have recursive recalls. Now for these fs I get one from each recursive insertion of the uh uh recurrence relation. And so that means they collect different numbers of powers of a, different numbers of a's. And of course also the uh arguments are not always the same. They go down by different amounts of b's. And if you work it out, you find you have to sum from zero up to k minus one and then it's j a's up front and jb's inside the argument.
9:30 That's literally just inserting. And you can prove by induction that this is the right thing if you if you want to be formal. Now we can insert what we know about uh k. This k is log base b of n and a to the power log base b of n. You can rewrite logarithm rules. That's the same as n to the power log base b of a. And remember this was our constant c that we looked at in the master theorem. This was driving exactly which case applies. So overall this is the number of leaves multiplied by the cost for one leaf. This was the orange uh contribution. Was it orange? Sorry.
10:14 Yeah. Yeah. The orange the leaves are orange. Okay. That's the contribution of the leaves. Whereas this is the collected contribution the purple part along all the recurrences. And that's a bit harder to say how big that is. But that's the two contributions. The three cases of the master theorem come precisely from whether that dominates asmtoically or whether they're balanced and they both dominate. They both contribute.
10:50 And to see algebraically what happens um you want to assume somehow to make things a bit simpler. Let's assume that this function is just a power polomial n to some alpha some power alpha. Then you can rewrite this guy these guys as a to the j f of this thing is just the argument to the power alpha and by rearranging the terms. So this is n to the alpha that goes to the front. You have a to the j and you have b to the j times alpha. So you can pull the b to the alpha in and then you have two uh terms with power j. These combine as a divided b to the alpha to the j and that you can again split if you um use this uh easier if you insert it and and work backwards. What it comes down to is a power of b where now the exponent here has this contribution c minus alpha. That's precisely the comparison between uh this term that's the c right and alpha the power from the toll function and you see if uh if c is larger than alpha then this b to the j that's an exponentially growing term whereas if alpha is larger than c then this has a negative exponent so it's exponentially decaying that's where the two extreme cases come from this this uh contribution of the internal levels is a geometric series.
12:23 Now this is just a constant in terms of J and this is a power some some constant to the power J. So this sum you can rewrite and even give a closed form because for for this simple case it's just the geometric sum and um you see where whether this has a dominant contribution or not. uh if alpha is less than c then this has a positive contribution then this this term dominates and uh the the leafs win and this one So if alpha is less than c, the exponent here is positive.
13:46 That seems to mean to me that there's a a b. I wanted to not do the full details here. Enter the alpha and then we have this B to the C minus alpha J.
14:21 Uh, the point is we sum this uh until this log term. So I can put log base b of n here. The n to the alpha is just a constant in the in the front. And by and large this uh in the case where alpha is less than c.
14:42 This is larger than zero. And so uh I have some positive uh number greater than one to the power j. So the last last term will contribute. The most important term is is this last term.
15:18 As you see this this becomes together with the base of B and N to the power C minus alpha and then it works out to N to the C which is indeed what we have here. Uh I guess last term of the sum is here. Okay, that's what what this what this also says. Sorry for the confusion. uh the last sum of this dominates because it's an exponentially growing term. And that means uh the largest J where you recurse all the way down, that's the leaves that win. Indeed. Okay. All correct.
15:56 That's the algebraic route. Uh I see how you see how you can justify all that I've shown you just from that. But I think it's way less intuitive than the visual version and much easier to get get tripped up in all the sign changes. Um, yet another way to draw the same derivation is as a recursion tree. That's maybe um this is from from the Corman book. That's the more usual way to draw this. So you have a topmost recursive call that costs f of n. Maybe you have a recursive calls here. three are shown where each time now the input size is is smaller by a factor B and then you can sum across the levels then this sum across the levels is precisely our sum here and then you have the contribution at the bottom now this is fine um the picture is memorable I find it doesn't really explain which case dominates all that well so I'd rather have you keep in mind uh these pictures uh from top to bottom is topmost recursive call, first level of recursion all the way down to the leaves, leaves at the bottom. So it it shows the same kind of tree. But the picture that is drawn here in purple is really the the sum of the costs across the entire level. And then you see which of the three cases applies depending on whether that shape turns to something that's just flat at the bottom, flat at the top, or uh balanced everywhere, a rectangle across the thing.
17:31 Because we're doing this here with a little bit more mathematical rigor, let me mention a few things. Um, in usual algorithms and it was the case for merge sort as well, we actually have floors and ceilings or some sort of rounding to deal with when we do recursive calls. We cannot really in general divide by two and assume this is all fine. So the usual the actual recursion for merge sword was more of this form that you have one call where n is rounded n half is rounded down and one call where n half is rounded up and then your 2n um that doesn't really fit the master theorem as we stated it. So technically it's not applicable to this unless you assume n is a power of two and you can do that. But maybe you ask yourself the question what if I don't want to do that. Can I not somehow argue still that this works and um it does under a mild condition that almost always will be true. So if we ask you to do a formal proof usually you can appeal to this this trick here.
18:38 The first point here is that if you have uh floors and ceilings in the actual recursion you can solve a different recurrence t prime where you ignore those And we're now indeed this is um okay t prime here as well. This is a function that's defined for all real values n which you need here because you're just dividing by two. And it turns out you can still argue this is a function with a real a real function from reals to reals. You can still argue about limits. You can still talk about the theta class of this function. none then just the same. Um but it's not always the case that the theta class for t prime and the theta class for t are the same. You can come up with nasty examples where they are not depending on what this function f here is. But if f satisfies this polomial growth condition then you can guarantee that this always works.
19:43 Um this is maybe not the precise characterization of when this works. It's one way to do it. So it says uh there's an n0 from which on this holds and then for every um distance for how much you scale your n up or down well up from n up to capital t * n your function should not vary by too much should be within a constant factor d and you see that all polomials satisfy this that's why it's called polomial growth condition and again this is a research Arch paper that that studied this I don't expect you to uh go through that. Um all I want to say here is that um if your tall function satisfies this then you can ignore floors and ceilings and the theta class is unaffected. Uh in general this is independent of the regularity condition which is the other annoying thing when applying the master theorem. All of this aside, um, so here's a general recipe. All all fs that satisfy this. So any any f that is a power of n and maybe a power of a log and maybe even a power of a log log. Not that we ever use examples like this in algorithms that we study, but in principle maybe it shows up. All of such functions satisfy this condition up here. That's already covering a lot. And the important part of this slide really is this box because that's what you will apply in virtually all of the recurrences that we care about. If the tall function is asmtoically equivalent to some constant times what I just said n to some power and these these powers here can all be zero. So it could also just be 2 * n. Right? That would be for our merge sort that would be one example. any function that satisfies this and uh when you're in the right case of the master theorem then it satisfies both this polomial growth condition and the regularity condition and you can just quote that fact and not worry about it.
21:56 I always felt the master theorem is more technical to apply than it should be because of this annoying regularity condition and it turns out indeed you can always under this assumption prove it in general. So let's not do it each time we apply it. Okay, you're allowed to use this without proof in in exercises and exams etc. Uh all you need to remember is they have to check that the function is of the correct form.
22:36 So let's uh see if that has sunk in enough. Here's um another recurrence. This time definitely I'm not going to show the theorem again. Try to remember from the pictures and the pneummonics what the solution here should be.
22:59 So one thing I'll give you for free even though it's not relevant here our f of n login this is of the form that it satisfies the regularity condition and the polomial growth condition by the box from before.
25:05 Okay, let me um start sharing. Anyone still thinking in the room? Uh let me show you the the range of different answers. It's a bit of a a gotcha question and that's um it's easy to be tripped by it. Now, one option is to show you again um in the tool what happens.
25:49 I'll I'll switch to that then. Um that's what the recurrence looks like. Uh before I'm going to show um what will happen, let's first do the brute force application of the master theorem. First of all, we have to compute this constant C. It's very easy here, right? Log of a a thing is always one. So I should compare my function f with n to the power one n. Now here um it's true that n login grows faster than n. So what we should see is that uh the kind of topmost part is a bit more expensive. The further I go down, the less expensive my uh overall levels get. You initially don't see this that that much, but ultimately uh you see how it it gets to this shape. So maybe um what we should expect is that the the topmost dominates which would be k and then we would get as the solution here n to the well just f so theta of n login.
27:03 Now if you look at the limit shape though this is not everything dominated by a line at the top. Indeed we get this funny triangle.
27:13 So um it seems it's not true that just the first call dominates everything even though it is growing faster than n. Uh but it's not growing faster by enough to completely dominate this. And what you see here is is kind of you can still work out the correct answer from this. We still have the topmost call that costs n login. That's the width of that. If say in a more geometric way, if I were to cut this open here and rotate that triangle here, then I have a a rectangle that's half as wide but equally tall, right? So, ignoring constant factors, I should still have width time height. The width is n login and the height is log n. So, we should expect n log squar n. And that's also the right answer. uh it's shown here as well because the the tool tries to be more clever than just applying the master theorem but it does tell you the master theorem gives no answer.
28:14 So the right answer here also is uh no need to change your answer now. Um it doesn't apply so it doesn't make any statement. As you've seen we can reason ourselves to the at least the guess that the answer should be nlock squared n but it doesn't follow from the master theorem. It just it's not of satisfying any of its uh assumption.
28:41 Let me show this in large again. Why? The three cases have these conditions. We compare n to the power c n in our case um to our function f and it's not true that f n login is theta of n right it's growing faster. So we could try the last condition but n login also doesn't grow faster than n to the power 1.01 or something like this. there's no epsilon you can add to the power to make that statement true. So there's a gap between these three cases where precisely a function like n login for the toll function falls between the cracks in this formulation. Anyways that's what happens. uh the triangle shape gives the right intuition and you can prove indeed the the solution is n log squ n but roughly uh well you want to use a bit more of an algebraic method. The formal proof of this recurrence I would consider a little bit at the edge of the scope. Um you can in this specific example just write down what the levels cost and and sum them up. Uh but that is not really my focus. You should be able to apply the master theorem where it applies and you should recognize where it doesn't apply.
30:05 And then maybe an ad hoc transfer question is whether you can still solve the recurrence there. But that is not part of the very required part.
30:28 Okay. So here we can't make a statement. What if you need to solve such a recurrence? I'm um uh giving you some recipe here that this this whole thing will not be part of the exam material. This is one of those slides where I'm just trying to convince you there's more than we teach in in uh first and second year courses. And maybe you find this useful even if you have a more general recurrence. This looks a bit scary, but let's take it apart a little bit. There's again some toll function f. There's some base cases. Same as before. Now, instead of having um a times a recursive call for n divided b, I now have um a sum here. So, I can have a different number of calls for different subpros sizes. I may have different calls that chunk up the problem differently. And I'm even allowed to add these little error terms. These R&Ds should be small so that you can eat the rounding inside there in a bit more of a general sense.
31:31 So this is almost any recurrence that you will get from a dividing conquer algorithm. Um it also makes this stronger assumption right off the bat that your your toll function here is asmtoically equivalent to some nice form. So it's it's a bit more narrow in in that sense, but then it gives you a much stronger statement. Um instead of this constant C log base B of A, you now have to compute a slightly more complicated uh term is still a constant. All that it depends on is the the ADS and the BDS. And alpha is this exponent here from f of n. This is some number for any specific recurrence. You can just plug in what it is and based on what this h is the theorem tells you the full solution of this recurrence. In many cases even including the complete constant it gives you the constant factor of the leading term as well.
32:32 So there's uh there's the cases h is less than zero, h is larger than zero and h is equal zero which splits further depending on what this this uh exponent of the log is. So if we just um apply it to our recurrence from a second ago 2 * t of n half plus n login then um we would have alpha = 1 and gamma also one. These are from from the toll function. Uh what would h be?
33:06 It's one minus this scary looking sum. But here it's really just one term, right? we have a just one recursive term. So it's 2 * and then 1 / b to the power alpha. So one that is just zero right so we're in this case here where we have to check what gamma is and in our case uh gamma is one so we're in this case that I underlined gamma is greater than minus one so the solution should be asmtoically equivalent to this constant 1 / f tilda that is uh this term Here I'm not going to compute that. You can if you if you feel like plug it in and work it out. And then times f of n which in our case is just n login and times uh no touchcreen is going nuts. Um give me a sec. Well we have another factor login coming from the the third case and that's it. Right. This is uh and that's where uh you get this
← Video 5-1: Divide and Conquer recurrencesVideo 5-3: Selection by Rank, Quickselect →