Chapter 4: Divide-and-Conquer: Recurrences and Matrix Multiplication

Welcome to Last Minute Lecture.

This free chapter overview is designed to help students review and understand key concepts.

These summaries supplement, not replace, the original textbook and may not be redistributed or resold.

For complete coverage, always consult the official text.

Ever feel like you need to get up to speed on something, but you want to do it like really quickly and thoroughly?

Well, that's what we're all about here, right?

And today, we're going to take a deep dive into this super powerful problem -solving technique, the divide and conquer method.

You got it.

We've got some really cool material to work with today that lays out this really elegant strategy that, honestly, you see everywhere.

It's all about, at its heart, taking these big gnarly problems and breaking them down, making them smaller, more manageable, until they're actually pretty easy to solve.

Right.

Like if you're staring down this huge project, instead of freaking out, you just kind of don't get up into smaller steps.

Right.

Makes it way less intimidating.

And the thing is, this isn't just some abstract idea, it's the basis for a ton of really efficient algorithms out there.

And the really interesting thing is that we're not just going to look at how those algorithms work, but how fast they work.

And to do that, we're going to use some pretty clever math tools called recurrences.

Our goal today is to wrap our heads around the core ideas of divide and conquer and how these recurrences help us analyze their efficiency.

All right, so let's get down to brass tacks here.

Divide and conquer, it seems to have a pretty clear three -step process.

First up,

divide.

What exactly happens in this step?

So the divide step, you take your original problem and you split it up into smaller subproblems.

The key here is that these subproblems, they got to be smaller versions of the same problem, you know, just at a reduced scale.

Think of it like a fractal, I guess.

The same pattern, but just smaller.

Okay, right.

So we've taken our big complex problem and we've created a set of smaller, simpler, but similar problems.

What's next?

Next comes the conquer step.

This is where we actually solve these smaller subproblems, and we usually do it recursively.

But, and this is super important, you can't just keep dividing forever.

Eventually, those problems get so tiny that you can just solve them directly, no more dividing.

That's what we call the base case.

The base case.

The problem is so simple, you just know the answer right off the bat.

Like if you're sorting a list and you get down to one item, well, it's already sorted.

Exactly.

That's the stopping point for the recursion.

Otherwise, you just keep going forever.

Okay, so we've divided,

we've conquered these tiny problems.

What's the last piece?

The final step is combine.

We take all those solutions from the smaller subproblems and we piece them back together in a very specific way to get the solution for that big original problem.

How we combine them really depends on the problem we're trying to solve.

So it's this cycle, break it down, solve the little pieces, assemble the solutions until we have the answer to the big one.

Quite elegant, actually.

It is.

And this whole recursive nature of divide and conquer, this is what leads us to how we analyze how efficient these algorithms are, how long they take to run.

That's where those recurrences come in.

Recurrences.

Yeah.

They sound kind of scary, but they're really just about using math to describe this divide and conquer thing in terms of running time, right?

It's a good way to think about it.

They're basically equations that define a function based on its values with smaller inputs, like a self -referencing formula.

So what does a typical recurrence look like when we're talking about algorithms?

Well, a general algorithmic recurrence usually has a couple of key parts.

First, it'll include what we call recursive cases.

These are parts of the equation where the function basically calls itself, but with smaller inputs.

That mirrors the conquer step in our divide and conquer strategy.

And then it'll also have one or more base cases.

These specify the value of the function when the input is small enough to solve directly, just like the base case in the algorithm itself.

Right.

So the recurrences are all about figuring out how long the divide and conquer algorithm takes as the input size grows.

Right.

And to make sure they accurately reflect the running time, particularly with large inputs, let's say anything bigger than some threshold, call it fine dollar dollars.

These algorithmic recurrences got to meet a couple of conditions.

What are those?

First, if the input is smaller than that threshold, then dollars dollars, the algorithm should take a basically constant amount of time to run.

We show this with the big theta notation as theta.

That just means the time stays the same no matter how big the input gets within that small range.

And second, for any input larger than or equal to dollars dollars, the recursive process should always end up at one of those base cases.

We don't want it to go on forever.

Right.

Makes sense.

Got to be sure the algorithm will actually finish.

And I think we have a note here about a convention regarding base cases in recurrences.

Yeah, it's pretty common when you're writing these recurrences that you don't always spell out the base case.

If it's not there, we just assume that it's an algorithmic recurrence and that the base case is there implied.

The nice thing is for most of the recurrences we see, the exact value of that den dollars and even whether we're rounding up or down the input size when we divide doesn't really change the overall way the running time scales as the input grows.

Gotcha.

So let's try this out on a real example.

We have this basic divide and conquer strategy for multiplying matrices.

What's the idea there?

OK, so you've got two matrices, same size, one times MN dollar, let's call them A and B, and we want to multiply them.

Get a new matrix C.

A simple divide and conquer approach is to divide each of those matrices into four smaller matrices, each one $2 times N22.

OK, so our big matrices get chopped up into four smaller ones.

Then you can do the matrix multiplication by recursively multiplying these smaller pieces and adding them together in a certain way.

And if you count up all those recursive multiplications and additions, you'll find that the running time can be described by this recurrence, $2 ATN2 plus theta $1.

So we have eight recursive calls, each working on a problem half the size plus some constant amount of work for the addition.

So what does this tell us about the total time to multiply these matrices?

Well, when you solve this recurrence, you get theta and three.

Hold on, theta and three dot.

But isn't that the same running time as the regular, like, brute force way of doing matrix multiplication with three nested loops?

You're exactly right.

It is the same.

On the surface, this divide and conquer approach doesn't seem to be any better in terms of how the runtime scales with the input size.

That's weird.

I would thought breaking things down would make it faster.

Why not here?

Our notes mention this idea of a bushier recursion tree compared to something like merge sort which we might deep dive into another time.

Because we have eight sub problems at each level of the recursion, the total work just blows up quickly, and that leads to the 23 -3 complexity.

You'd think the smaller problems would help, but the overhead from those eight recursive calls at each step, that outweighs the benefits, giving us the same cubic time complexity as the direct approach.

So just using divide and conquer doesn't automatically mean a faster algorithm.

But there's this Strassen's algorithm that's supposed to be more clever.

What makes it different?

Strassen's algorithm is a slicker way to do matrix multiplication.

It's still divide and conquer, but the trick is that it only makes seven recursive calls on those $2 x n to 2 matrices, not eight.

Seven instead of eight?

Doesn't sound like much, but I bet it makes a big difference in the end, right?

Big difference.

While it cuts down on the recursive multiplications, Strassen's algorithm does have some extra additions and subtractions with those smaller matrices, but those only take theta and n2.

So the recurrence for Strassen's algorithm looks like this.

T n dollars, 7 T n 2 plus theta and 2 2.

Seven recursive calls plus some theta and $2 work for the extra additions and subtractions.

So the solution to this recurrence is where we see the speed up.

Precisely.

When you solve it, you find that theta and nT and A, now $2, F and E, 7, that's log base 2 of 7, and it's about 2 .81, so the running time is like $1 into $2.

Whoa, that's definitely better than theta and n3.

Just by being a bit smarter about how we divide and combine, we get a much faster algorithm for large matrices.

I wouldn't have guessed that cutting out one recursive call would make such a huge difference.

That's the key takeaway here.

Strassen's algorithm shows us that sometimes, doing a bit more in that combine step here, the extra additions and subtractions that can actually let you make way fewer recursive calls, leading to a more efficient algorithm overall.

The multiplication, especially when it's recursive, that's the real bottleneck here.

Strassen's genius is not only in doing fewer multiplications, but in choosing exactly the right seven products to compute.

Then, with some clever additions and subtractions, we get the final answer without needing that eighth costly multiplication.

More additions and subtractions, but fewer multiplications.

And for big matrices, that trade -off really pays off.

Now we've seen how these recurrences help us figure out the efficiency, but how do we actually solve them to get those theta bounds?

And those talk about a bunch of different methods.

Yeah, there are a few powerful techniques for solving recurrence relations.

Our notes focus on three main ones.

The substitution method, the recursion tree method, and the master method.

And they also touch on this more advanced method called the Acrobotsy method.

Let's start with the substitution method.

Does that mean we just guess the solution and then check if we're right?

That's the gist of it.

First, you make an educated guess about what the solution should look like.

You might include some unknown constants in your guess.

Then, you use mathematical induction to prove that your guess actually works and to figure out what those constants should be.

To get a tight theta bound, you'll usually have to prove an upper bound using big O and a lower bound using big omega separately.

Induction.

That takes me back.

We'll need a base case for our induction too, won't we?

You bet.

And when you set up your inductive hypothesis, make sure you're working with actual inequalities and constants, not just big O or big omega notation.

You establish the asymptotic bound only after the induction is all done, and you've pinned down those constants.

We've got this example of recurrence in our notes, 2tq, 2tl -floor, n2, all -floor plus theta n -floor.

How would we go about solving that with the substitution method?

A good guess for that one is that the solution is 1lglana -di.

Then you use induction, assuming that for some dollars less than lg -nlga for some positive constant stators.

Then you've got to use that assumption to show that the lg -n -nlga also holds.

And that theta and term in the original recurrence, that's going to be key in making the induction work.

Sounds like coming up with a good guess is half the battle.

Are there any tricks for that?

For sure.

Look at recurrences you've seen before and know the solutions for.

Sometimes it helps to start with some loose upper and lower bounds on the solution just to get a sense of how fast it's growing.

Our notes even mention this neat trick.

If your induction hypothesis isn't quite strong enough, you can try taking away a smaller term from your initial guess.

That can sometimes give you just enough wiggle room to make the induction go through.

Cool.

So guess, prove with induction, and be careful about how we use the big O and big omega notation.

Got it.

What about this recursion tree method?

It sounds like it's more visual.

It is.

The recursion tree method is all about visualizing the cost of the algorithm as a tree.

Each node in the tree represents the cost of a subproblem at some level of the recursion.

The root of the tree is the original problem, then its children are the subproblems after the first division, and so on.

So we turn the problem into a tree, and then we look at the cost at each level.

Yeah.

The first thing you do is figure out the cost of the work done at each level, the cost of splitting the problem, the cost of combining the results, and the cost of all the subproblems at that level, not including the recursive calls they make.

Then you add up those costs across all the levels, and that gives you an estimate of the total cost.

And that sum is the solution to the recurrence.

Well, the recursion tree method is really great for coming up with a good guess for the solution.

It's visual, so it's usually easier to see what's going on than just trying to think up a solution.

But to be totally rigorous, you should really check that guess with the substitution method.

Here's an example from the notes.

3tnt, 3tn4, plus theta n2 water.

How would we use the recursion tree for this one?

In this case, at each level, one problem of size in dollars is split into three subproblems, each sans sure in the size.

The cost of the work at the root is theta n2 dollars.

Then at the next level, there are three subproblems.

Each is sized sun to fours, and each of those would have a cost of theta, which is theta n216 dollars.

So the total cost at that level would be three times that, which is theta, three n216 dollars.

And as you go down the tree, the problem sizes get smaller, and the cost at each level shrinks too.

By analyzing the sum of all those costs, all the way from the root to those base cases, you can usually get a good idea of how fast the algorithm's runtime grows.

For this specific example, the total cost ends up being dominated by what's done at the very top, which suggests a solution of thalers.

And what about unbalanced recursion trees, like 2n3 plus t2n3 plus theta?

That seems like it could get messy.

Definitely.

When the subproblems at each level have different sizes, the tree gets lopsided.

In this example, one branch of the recursion gets smaller by a factor of three each time, while the other only shrinks by 32, becoming 2n333.

You still analyze the cost at each level, which is theta in here, but you gotta be careful about how deep the tree is.

The shortest path to a base case will be shorter than the longest one.

The total running time will depend on the length of that longest path, because that's when all the subproblems have been solved.

Figuring out the total work means considering the cost from all those levels, even though the tree isn't perfectly balanced.

So recursion trees, they're really useful for getting a feel for the cost and for making those educated guesses, which we ideally confirm with the substitution method.

And then we have the master method.

That sounds like a real time saver cookbook approach for solving recurrences.

Exactly.

The master method is all about having these formulas you can plug into for recurrences that fit a specific pattern.

tne equals atnb plus fn, literally, where $1 is the number of subproblems you created each step.

$b is how much the problem size shrinks, and a billers is the cost of the work you do outside of those recursive calls, like dividing and combining.

For this to work, it's going to be at least one, a biller is going to be strictly bigger than one, and they both need to be constants, and fee on any can be any function of any biller.

Okay, so how does this cookbook work?

What are the recipes here?

The master method boils down to comparing how fast that non -recursive part of the work, a band grows, compared to the work done way down at the bottom of the recursion tree, which has to do with log.

There are three main cases based on this comparison.

Let's hear them.

Case 1.

If phi under grows polynomially slower than log o, meaning there's some constant, we'll call it epsilon, greater than zero, where 5n is this ballerando,

then the solution is dominated by the work done in those subproblems, especially at the bottom of the tree.

In this case, theta endo ends goes too.

It's like the recursive calls are the most expensive part.

If atnl is much smaller, the recursive calls dictate the overall time.

Case 2.

If theta endo is about the same rate as a noller, meaning it's theta nno for some constant galler greater than or equal to zero,

here nno is just the logarithm of 1s, then the solution has this extra logarithmic factor.

So if the non -recursive work and the recursive work are kind of balanced, we get that logarithmic bump in the time complexity.

Case 3 now.

If fnb goes way faster, meaning it's omega plus epsilon for some constant epsilon greater And if fnmaryl also follows a certain regularity rule, meaning fnb is less than or equal to cfn, for some constant senr is less than 1, and for large enough nno, then the solution is dominated by that non -recursive work.

In this case, late minera, this extra condition just ensures that the cost of the recursion doesn't explode too quickly compared to the cost at the top level.

So if the work we do in dividing and combining is the big kahuna, that's what determines the runtime.

Are there cases when the master method doesn't work?

Yeah, it's not a magic bullet.

It doesn't work if fmendary and sedary don't compare easily in terms of polynomial factors.

Like if fnr is something like nno that grows faster than any polynomial but slower than any exponential, and the master method might not give a direct answer if fmr grows almost as fast as nno, but not quite within a polylogarithmic factor like in case 2.

Also that polynomial separation by some epsilon dollars in cases 1 and 3 is super important.

The notes mention we can use the master method to analyze our matrix multiplication examples.

Right.

For the basic recursive matrix multiplication with the recurrence 8tn2 plus theta, we have

abababdafafetawatitosetatodeon, here's n31 which is just 2nm3, since theta, which is also 1 epsilon if we pick epsilon to be 1 for example, in case 1 in the master method applies and we get steta n3 just like before.

And for Strassen's algorithm where we had 7tn2 plus theta n2.

So in this case, the beta is dn2 and then our labal is down to 8n3 which is roughly n to $2 .89 and graval is roughly n to any 1 epsilon.

Now we can pair theta n, which is $2 sets in any 1 epsilon, we see that $2 and $2 cent if we choose epsilon to be something like .81.

So case 1 in the master method wins again and we get the solution theta n0.

Pretty neat how this cookbook method just spits out the same answers we got earlier.

Yeah.

Last one, the akrobotsy method.

This is for the real tough recurrences, right?

Yeah.

Akrobotsy is a more general, powerful method for handling those recurrences where the sub problems at each level might have different sizes.

The general form it handles is like this, tier -am nanome n plus sum i1 tnb a.

So you can have two different sub -problems each with its own coefficient abn and scaling factor b dollars.

That looks intense.

How do we even start solving that?

The first big step in akrobotsy is finding this unique real number, we'll call it p im, that solves the equation sum e me plus a me.

Once you've found that claim then the general solution for tn me is given by this more complicated formula with an integral, theta np1 plus int x xp plus 1dx.

An integral.

Okay, now we're getting into some serious math.

Our notes do point out that there's a polynomial growth condition on the function for often dollar that often lets us ignore those pesky floor and ceiling functions when using akrobotsy.

And they give an example, tmn plus t7 and 10 plus n dollar.

To solve this one, you'd first need to find tb in the equation, $15 p plus 710 p plus And after you've got peel, which the notes say is about .84, you plug it into that general formula and work out the integral to find the asymptotic solution for fn.

So akrobotsy is like the heavy artillery we bring out when the simpler methods don't cut it.

Especially when our sub -problems have different sizes.

Exactly.

All these methods together, substitution for direct proof, recursion trees for intuition, the master method for quick solutions to common forms, and akrobotsy for the more general cases, they give us a whole toolbox for understanding how efficient these divide and conquer algorithms are.

And as the notes stress, practice is key.

Working through different problems, seeing how these methods apply in different situations, that's how you really get a handle on them.

This has been a real deep dive into divide and conquer, recurrence relations, matrix multiplication, and all the ways to solve those recurrences.

We've walked through those three fundamental steps, divide, conquer, combine.

We've seen how recurrences help us describe how fast they run.

We've even looked at that surprising case of basic matrix multiplication and how Strassen's algorithm does it better.

Plus, we've examined a whole bunch of techniques for solving those recurrences, from simple substitution to the more hardcore akrobotsy method.

And what's amazing is how this simple idea of breaking problems down can lead to such elegant and often super -efficient algorithms.

And then these mathematical tools, they let us really understand and compare how those perform as the problems get bigger and bigger.

So for you, dear listener, the next time you're facing a challenge, whether it's at work or just something you're curious about, think about whether you could use this divide and conquer approach.

Could you break that big, scary task down into smaller, more manageable pieces?

And now that you've got a glimpse into how we analyze algorithms with math, what other problems could benefit from a similar kind of rigorous systematic approach?

In this Deep Dive, we've covered every major point, theory, finding, and example from this chapter on divide and conquer, recurrence relations, matrix multiplication, and the methods for solving them.

We've explored the core ideas, looked at examples, and talked about how to analyze the efficiency of these powerful algorithmic strategies.

That's it for today's Deep Dive.

See you next time.