The primary topics in this part of the specialization are: asymptotic ("Big-oh") notation, sorting and searching, divide and conquer (master method, integer and matrix multiplication, closest pair), and randomized algorithms (QuickSort, contraction algorithm for min cuts).
Formal Statement
Loading...
From the course by Stanford University
Divide and Conquer, Sorting and Searching, and Randomized Algorithms
1834 ratings
From the lesson
Week 2
Divide-and-conquer basics; the master method for analyzing divide and conquer algorithms.
Meet the Instructors
Tim RoughgardenProfessor
Computer Science
So having motivated and hyped up the generality of the master method and
its use for
analyzing recursive algorithms, let's move on to its precise mathematical statement.
Now, the master method is, in some sense, exactly what you want.
It's what I'm going to call a black box for solving recurrences.
Basically, it takes an input a recurrence in a particular format and
it spits out as output a solution to that recurrence,
an upper bound on the running time of your recursive algorithm.
That is, you just plug in a few parameters of your recursive algorithm, and
boom, out pops its running time.
Now, the master method does require a few assumptions,
and let me be explicit about one of them right now.
Namely, the master method, at least the one I'm going to give you,
is only going to be relevant for
problems in which all of the subproblems have exactly the same size.
So for example, in merge sort, there are two recursive calls, and
each is on exactly one half of the array.
So merge sort satisfies this assumption, both subproblems have equal size.
Similarly, in both of our integer multiplication algorithms,
all subproblems were on integers with n over 2 digits,
with half as many digits, so those will all also obey this assumption.
If for some reason you had a recursive algorithm that recursed on
a third of the array and then on the other two-thirds of the array,
the master method that I'm going to give you will not apply to it.
There are generalizations of the master method that I'm going to show you
which can accommodate unbalanced subproblem sizes, but
those are outside the scope of this course.
This will be sufficient for almost all of the examples we're going to see.
One notable exception, for those of you that watched the optional video on
a deterministic algorithm for linear time selection, that will be
one algorithm which has two recursive calls on different subproblem sizes.
So to analyze that recurrence,
we'll have to use a different method, not the master method.
Next I'm going to describe the format of the recurrences to which the master
method applies.
As I said, there are more general versions of the master method which apply to even
more recurrences.
But the one I'm going to give you is going to be reasonably simple, and
it will cover pretty much all the cases you're likely to ever encounter.
So recurrences have two ingredients.
There's the relatively unimportant, but still necessary, base case step.
And we're going to make the obvious assumption, which is just satisfied by
every example we're ever going to see in this course, which is that at some point,
once the input size drops to a sufficiently small amount,
then the recursion stops, and the subproblem is solved in constant time.
Since this assumption is pretty much always satisfied in every problem
we're going to see, I'm not going to discuss it much further.
Let's move on to the general case where there are recursive calls.
So we assume the recurrence is given in the following format.
The running time on an input of length n is bounded above by some number
of recursive calls, let's call it a different recursive calls.
And then each of these subproblems has exactly the same size, and
it's 1 over b fraction of the original input size.
So there's a recursive calls, each on an input of size n over b.
Now, as usual, there's the case where n over b is a fraction and not an integer.
And as usual, I'm going to be sloppy and ignore it.
And as usual, that sloppiness has no implications for the final conclusion.
Everything that we're going to discuss is true for
the same reasons in the general case where n over b is not an integer.
Now, outside the recursive calls, we do some extra work.
And let's say that it's O(n to the d) for some parameter d.
So in addition to the input size n,
there are three letters here which we need to be very clear on what their meaning is.
So first of all, there's a, which is the number of subproblems,
the number of recursive calls.
So a could be as small as 1 or it might be some larger integer.
Then there's b.
b is the factor by which the input size shrinks before a recursive call is
applied.
b is some constant strictly greater than 1.
So for example,
if you recurse on half of the original problem, then b would be equal to 2.
It better be strictly bigger than 1 so that eventually you stop recursion, so
that eventually then you terminate.
Finally, there's d, which is simply the exponent in the running time of the,
quote, unquote combine step, that is,
the amount of work which is done outside of the recursive calls.
And d could be as small as 0,
which would indicate constant amount of work outside of the recursive calls.
One point to emphasize is that a, b, and d are all constants.
They're all numbers that are independent of n.
So a, b, and d are going to be numbers like 1, 2, 3, or 4.
They do not depend on the input size n.
And in fact, let me just redraw the d so that you don't confuse it with the a.
So again, a is the number of recursive calls and d is the exponent and
the running time governing the work done outside of the recursive calls.
Now, one comment about that final term, that big O(n to the d).
On the one hand, I'm being sort of sloppy.
I'm not keeping track of the constant that's hidden inside the big-O notation.
I'll be explicit with that constant when we actually prove the master method.
But it's really not going to matter.
It's just going to carry through the analysis without affecting anything.
So you can go ahead and ignore that constant inside the big-O.
Obviously, the constant in the exponent, namely d, is very important.
So depending on what d is, depends on whether that amount of time is constant,
linear, quadratic, or so on.
So certainly we care about the constant d.
So that's the input to the master method.
It is a recurrence of this form.
So you can think of it as a recursive algorithm which makes a recursive calls,
each on subproblems of equal size, each of size n over b,
plus it does n to the d work outside of the recursive calls.
So having set up the notation, I can now precisely state the master method for you.
So given such a recurrence, we're going to get an upper bound on the running time.
So the running time on inputs of size n is going to be upper bounded by
one of three things.
So somewhat famously, the master method has three cases.
So let me tell you about each of them.
The trigger,
which determines which case you're in, is a comparison between two numbers.
First of all, a, recall, a is the number of recursive calls made.
And b raised to the d power.
Recall, b is the factor by which the input size shrinks before you recurse.
d is the exponent in the amount of work done outside of the recursive call.
So we're going to have one case for when they're equal,
we're going to have one case for when a is strictly smaller than b to the d.
And the third case is when a is strictly bigger than b of the d.
And in the first case, we got a running time of big O of n to the d times log n.
And again, this is d, the same d that was in the final term of the recurrence.
Okay, the work done outside of the recursive calls.
So the first case,
the running time is the same as the running time in the recurrence,
outside of the recursive calls, but we pick up an extra log n factor.
In the second case, where a is smaller than b to the d,
the running time is merely big-O of n to the d.
And this case might be somewhat stunning that this could ever occur,
because of course, in recurrence, what do you do?
You do some recursion, plus you do n to the d work outside of the recursion.
So in the second case, it actually says that the work is dominated by
just what's done outside the recursion in the outermost call.
The third case will initially seem the most mysterious.
When a is strictly bigger than b to the d,
we're going to get a running time of big-O of n to the log base b of a.
Where, again, recall, a is the number of recursive calls and
b is the factor by which the input size shrinks before you recurse.
So that's the master method with its three cases.
Let me give this to you in a cleaner slide to make sure there's no
ambiguity in my handwriting.
So here's the exact same statement, the master method
once again with its three cases, depending on how a compares to b to the d.
So one thing you'll notice about this version of the master method is that it
only gives upper bounds.
So we only say that the solution to the recurrence is big-O of some function.
And that's because if you go back to our recurrence,
we used big-O rather than theta in the recurrence.
And this is in the spirit of the course, where as algorithm designers,
our natural focus is on upper bounds, on guarantees for
the worst case running time of an algorithm.
And we're not going to focus too much most of the time on proving stronger bounds in
terms of theta notation.
Now, a good exercise for
you, to check if you really understand the proof of the master method after we go
through it will be to show that if you strengthen the hypothesis and
you assume the recurrence has the form T of n equals a times T of n over b plus
theta of n to the d, then in fact, all three of these big-O's in the statement of
the master method become thetas and the solution becomes asymptotically exact.
So one final comment.
You'll notice that I'm being asymmetrically sloppy with the two
logarithms that appear in these formulas.
So let me just explain why.
In particular, you'll notice that in case one, with the logarithm,
I'm not specifying the base.
Why is that true?
Well, it's because the the logarithm, with respect to any two different bases,
differs by a constant factor.
So the logarithm base e, that is, the natural logarithm, and the logarithm base
2, for example, differ by only a constant factor independent of the argument n.
So you can switch this logarithm to whatever constant base you like,
it only changes the leading constant factor,
which of course is being suppressed in the big-O notation anyways.
On the other hand, in case three, where we have a logarithm in the exponent,
once it's in the exponent, we definitely care about that constant.
Constants is the difference between, say, linear time and quadratic time.
So we need to keep careful track of the logarithm base
in the exponent in case three, and that base is precisely b,
the factor by which the input shrinks with each recursive call.
So that's the precise statement of the master method,
and the rest of this lecture will work toward understanding the master method.
So first, in the next video, we'll look at a number of examples, including resolving
the running time of Gauss's recursive algorithm for integer multiplication.
Following those several examples, we'll prove the master method.
And I know now these three cases probably look super mysterious,
but if I do my job, by the end of the analysis,
these three cases will seem like the most natural thing in the world, as
will these somewhat exotic looking formula for exactly what the running time is.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
