Video 5-1: Divide and Conquer recurrences
CS 566 – Efficient Algorithms (Winter 2026-27) · unit page
· YouTube
2026-11-09, 16:30
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:02 In unit five, we'll learn about the first design principle for algorithms that you can apply to many different projects or many different uh algorithmic problems and uh tie together observations from the previous chapter in sorting. But we've essentially seen examples of this design pattern divide and conquer already without maybe dwelling too much on that fact. But here we will um I want to I wanted to show you uh what this looks like and how you can use it. But before we get there, this time we flip things around. We'll first talk about the analysis of algorithms that come out of this design pattern because they have always the same kind of rough shape. And it's good to be able to quickly have a a a rough estimate for their running time to see if it's worthwhile pursuing this route or not. And then we'll see um various examples of this design method. First of all, where does this name come from? Uh divide and conquer. Uh divided imper is the Latin origin. And I think it has origins also in Latin politics where uh I think even Julius Caesar used it. So if you can if you can divide your enemies somehow against each other, then they're easier to uh dominate. Um so maybe uh Same as in algorithms. Um, also in politics, it's easier if you have small scattered sub problems to somehow deal with them one by one instead of having this initial big problem in front of you.
1:41 Now, a bit less um uh antagonistic for algorithms will really think of divide and conquer in a very narrow sense. um it should always have these these steps where we take a large instance of some problem break it into smaller independent parts that's the divide part obviously then uh we recursively solve the sub problems using the same method applied to a smaller instance and then the less obvious case often the conquer step is how to derive a solution for the original problem from the solutions of the recursive problems and we've seen examples of that. Um, merge sort and quicksort are all classic examples. You could see binary search as an example as well. H you could maybe say that solution for towers of Hanoi is as you've seen in the tutorials you could also say is is a bit like that. Uh the last two are a bit more degenerate in that they only do one recursive call.
2:49 So they apply the same method on a single sub problem and then do something around conquer not true for tower of Hanoi. Sorry for that. Uh for binary search it's true for tower of Hanoi. We do two recursive calls one after the other. Uh for for merge sort the divide step is very simple. You just cut the array in the middle and the conquer step does all the work. namely the merging of the solutions of the sorted left and half, sorted left and right half. And for quicksort, it's the opposite. You first spend time with partitioning of splitting things and then uh the recursive the conquer step is just do nothing because after partitioning the left and right are sorted independently and don't need any conquering anymore. These are at the two extremes. In in general, you can have some effort before you recurse and some effort after you come back from the recursion. All of that is is allowed in principle.
3:54 We'll see many more examples later in this unit. Um before we go there, we'll talk about the analysis. And you know what? Let me not do this one. Let's rather do a concrete example. I have one coming up uh very soon. So in the first subsection of this unit, we'll talk about the analysis of algorithms that come out of this divide and conquer approach to designing algorithms. And we'll we've seen some examples like this before. Uh but uh let's um again uh think about the analysis from from first principles. is often useful to do that as a first step so you don't waste your time. The algorithms are usually recursive if you spell them out as divide and conquer. I say usually because I counted binary search as part of divide and conquer where you just have one recursive sub problem. There you might as well write it as a loop but you could write it as a recursive call. So instead of um having the the uh time being just written down, you often have a recursion a recurrence relation that tells you what the overall cost is. And we've seen of course examples of that. Uh in particular, merge sort had this lovely recurrence for the two parts where one is rounded up, one is rounded down because we can't split this middle element in half.
5:26 And we also I I mentioned at the time that yes there's a simple way to get a bound and yes there's a precise solution that you can spell out in terms of this periodic term that we've seen earlier today as well. Uh but a simple solution of this order n login is good enough to tell us yes this algorithm is nearlinear this is worth pursuing it's going to be fast. Whereas if the solution were n cubed, we would know not to pursue this as a sorting method. So while it's cool that you can work out these precise solutions as a first step, we don't need them. We need the rough order of growth only. And that's what this this section is about. Um there's a specific method, the master method that often lets you do that without too much work.
6:23 And here it is in its in all its beauty and glory. Uh it only works for certain cases of divide and conquer algorithms. So you should also I should stress that this is more about the methods that you can twist and tweak to certain examples to make it a bit more powerful. I'll present the simple cookie cutter version, the master theorem and uh we'll see how to twist and tweak that in a few examples um later in the chapter. But the stereotypical divide and conquer algorithm might do a certain number of recursive calls. So split the problem into a subpros each of size n divided b. Your principle a and b can be any numbers but um subject to the constraints. But let's also pin down for merge sort what we what we had the number of recursive problems for merge sort is two and uh I split it into halves. So to write that as n over b I have to put b also to two.
7:34 Now on top of that we need um a conquer cost which is the non-recursive effort that the algorithm spends for merge sort. That's merging. And if you want to be precise about what you count there, you can do element visits. So we could say for merge sort f of n was 2 * n. If we do element visits in the last in the adaptive sorting chapter, we got rid of the factor two and called it just merge co merge cost. Uh of course scaling by a factor two doesn't change how different algorithms relate to each other.
8:11 That's the cost we pay for the conquer step, the divide and conquer step. I guess the non-recursive part. And we have some base cases. If the input is below a certain threshold, we may not further recurse, but we might just solve the problem in some brute force way or for sorting for merge cost. Uh for merge sort, n0 could be um one. If we have a single element left then we don't need to do anything right. So for inputs of size zero and inputs of size one the merge cost merge sort cost is zero. We don't need to um do anything with these elements. So that's how merge sort maps into the framework. Uh under this assumption you can always write the overall cost of a method as this recurrence. it's the base case if the input is small enough and for larger inputs it's the non-recursive cost plus the recursive costs. So far so good.
9:16 Um with the caveat that uh we uh assume here that this that we apply this to um n a power of b so that it's clear what this n divided b should do. Um the other option is you say I'm treating this as a continuous recurrence. both can be made to work. For now, for the first time, for the first uh step, let's assume no rounding needs to happen. And I'm always just at a power of B so that the dividing division by B never leaves any uh remainders with that. The master theorem tells you how to solve these recurrences in most cases. Anyways, you compute this this threshold value C and you compare your non-recursive cost with that growth with that exponent C. And depending on what the outcome is, you are in one of the three cases. I suppose most people have seen this at that level in exactly this or a slightly similar version before.
10:29 So let's see if you remember by solving a concrete problem. Uh I mean I I can't go back to the previous slide to show you the theorem again. On the other hand, if you really internalized it, maybe you don't even need to see the theorem again.
11:44 And for the veterans from algorithms and data structures, you may or may not have spotted tiny details to what I presented there. I've ironed out a few rough edges. The base cases were a bit inconsistent. And so this is now the proper version that works that can be rigorously applied to the theorem to the recurrences we we deal with. I'll say more about that maybe another time.
12:32 Yeah, we had eight eight votes at some point earlier. So, getting close. Okay. So let me move move over here and um there is a slight majority is for the right thing. Um so it seems most people remember this but let's either way uh apply it. So maybe this is nicer on the other slide.
13:16 Here's our example. Now, all I need to do is pick apart the definition and the different values. The key that I need is this this constant C. And what I need to pick for that log B of A.
13:37 A is the number of subpros. That's two. And B is this factor that we divide by. So that's a half here. So I'm I'm comparing my function f the non-recursive part that's f I'm comparing that to n to the c. In this case it's precisely the same. So I'll be in this case two and in that case I can immediately write down the solution as whatever my my f is n to the c * login so square root login.
14:59 that's better. Okay, so this is uh one example where the master theorem immediately gives us the answer. Um as people found out, most people the majority found out uh square root n login is the right thing here. Um what could go wrong? Well, you could apply uh you could swap A and B. Then you would compute the wrong C. Then you would compare it with n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n squ in which case you might come to the conclusion that it's this uh uh it's bounded by n squ or you could maybe run into the last case I don't know. Um, one thing I should point out before we stop for today is that this last case unfortunately needs this regularity condition. So it has this slightly technical site condition because you're essentially here saying the solution for the recurrence coincides with the first recursive call. You need some assumption on this function f. I've always found that condition rather annoying because most of the times when you apply it, it's the very same proof that the regularity condition is satisfied. So I'll have some some sufficient conditions in a few slides that for almost all examples lets you skip to check this by hand.