0:21

So we'll have our recurrence at the top to just remind ourselves what that is.

Â Let's assume for the sake of argument that n is a power of b.

Â That's a reasonable assumption since we can always just pad n to be larger, right,

Â if we increase it by no more than b we can get to the next closest power of b and

Â then this will be a simpler analysis.

Â So we have our problem n.

Â At the next level, we break the problem down into

Â a copies of a problem n over b large.

Â 0:57

So level zero.

Â We have a problem of size n.

Â Level 1 we have problems of size n/b.

Â At the general level i we have problems of size n over b to the i.

Â At the bottom level, which is level log base b of n, we have problems of size 1.

Â 1:13

How many problems are there?

Â At level 0 there's of course one problem.

Â At level 1, a problems.

Â And in general at the ith level, a to the i problems.

Â At the log base b of n level, it's a to the log base b of n.

Â 1:48

And level one we have a problems.

Â And each of them takes O(n over b to the d) work.

Â Okay, we can pull out the a and the b and the d to be all together, and

Â that's just O(n to the d) times a over b to the d.

Â 2:17

Again, we can pull out the a to the i, the b to the i, and

Â we're left with O(n to the d)

Â times a over b to the d to the i.

Â And finally, at the bottom level it's just a to the log base b of n because

Â the problems are all size 1.

Â It's just O(n to the log base b of a).

Â 3:18

Just as well, we could have a geometric series that goes down.

Â So we could have, for instance, let's say 10,000,

Â 1,000, 100, 10, 1.

Â Where we're going down by a constant factor of ten at each increment.

Â Now it turns out, our multiplicative factor, let's call that r,

Â as long as r is not equal to one we have a simple closed form for this.

Â This is just a times

Â (1-r) to the n over 1 minus r.

Â And it turns out that big O notation,

Â what happens is we care about the largest term.

Â 4:01

So our sum is going to be bounded by a constant times our largest term.

Â So, if r is less than 1 then our largest term is the first element a and

Â therefore our solution is O(a).

Â Okay, because it's our largest term, it gets smaller,

Â smaller, smaller, smaller, smaller.

Â And as long as it's by this multiplicative factor,

Â then all that really matters is this first term,

Â because the rest of it sums to no more than a constant times that first term.

Â If on the other hand, r is greater than 1, then what matters is the very last term,

Â because that's the biggest term and all the previous ones are smaller and smaller.

Â So it's smallest, larger, larger, larger, largest.

Â 4:55

Now if we take that back to the case of our recurrence tree,

Â we notice our summation here.

Â This is the same summation we had from our recurrence tree and we see that we have

Â a geometric series.

Â a is taking the place of big O then to the d and

Â r is taking the place of a over b to the d.

Â So our multiplicative factor is a over b to the d.

Â And there are three cases.

Â You remember as we stated the solution to the Master Theorem.

Â Case one is d is greater than log base b of a.

Â Well it's equivalent to saying a over b to the d is less than 1.

Â So now we have our multiplicative term is less than 1.

Â So it's getting smaller and smaller and smaller.

Â That means that the largest term is the first term.

Â And that's the one that we have an order of.

Â So this is big O of, officially big O of big O of n to the d,

Â which is just the same as big O of n to the d.

Â 5:55

Case 2, where d equals log base b of a and equivalently,

Â a over b to the d is equal 1.

Â Well, if a over b to the d is equal to one, remember our geometric

Â series formula didn't hold, so we're going to just have to calculate this.

Â But if a over b to the d is 1, then a over b to the d to any power is still 1.

Â So that means, that our summation

Â 6:26

And that's just 1 plus log base b of n,

Â because that's the number of terms in our summation times O(n to the d).

Â Well the 1 is a low order term we don't care about, and log base b of n can

Â just be treated as log n, because a base change is just some multiplicative factor,

Â and that disappears in our big O notation.

Â So we end up with, as we see in the theorem, O(n to the d times log n).

Â And then our final case, is d is less than log base b of a,

Â which is equivalent to saying a over b to the d is greater than 1.

Â So here, our multiplicative factor is greater than 1.

Â So our smallest term is the first term and our largest term is the last term.

Â So in this case, this is big O of our

Â last term is O(n to the d) times a over b to the d to the log b of n.

Â So, i is log base b of n.

Â This is a bit of a mess.

Â Let's see whether we can fix this a little bit.

Â So let's go ahead and apply the log base b of n power separately to a and b to the d.

Â So we have, in the numerator, a to the log base b of n.

Â And then the denominator, b to the d times log base b of n.

Â Well, b to the log base b of n is just n.

Â So, that's going to disappear down to n to the d in the denominator.

Â In the numerator, a to the log base b of n,

Â by logarithmic identity is equal to n to the log base b of a.

Â So we can swap those other two.

Â 7:59

And now, if we compare big O of n to the d and n to the d,

Â we know big O of n to the d is bounded by some constant, k times n to the d.

Â So we have k n to the d divided by n to the d, which is just some k.

Â And that constant can go away because we're still talking about big O notation.

Â So we're left just with big O of n to the log base b of a,

Â which is what we have for the final case.

Â 8:30

I have a secret to tell you, however.

Â I do not remember the master theorem and

Â I don't actually even look up the master theorem.

Â Here's what I do.

Â When I have a recurrence of this rough form, I look at the amount of work

Â done at the first level and at the second level (which is a very easy calculation) and

Â then I just say to myself Is that the same amount of work?

Â If it's the same amount of work it's going to be the same amount of work

Â all the way down and so we're going to be in case two.

Â So it's going to be the amount of work at the first level,

Â which we known is O(n to the d), times log n because there are that many levels.

Â On the other hand, if the first term is larger than the second term

Â I know the first term is going to dwarf all the other terms.

Â And so, we're left with just O(n to the d).

Â And finally, if the first term is less than the second term,

Â I know they're going to keep increasing and it's the bottom term that I need.

Â