- 00:00:00 hi guys this is Keith Callie and today I
- 00:00:02 will be going over the master method to
- 00:00:05 solve recurrences and algorithms and
- 00:00:08 computer science the master method
- 00:00:10 provides a very simple way to solve
- 00:00:12 recurrences that take the following form
- 00:00:14 T of n equals some constant a times T of
- 00:00:21 n over B which is another constant plus
- 00:00:25 some positive function of n here so then
- 00:00:29 there's two constraints there's a
- 00:00:30 constraint a and it has to be greater
- 00:00:33 than or equal to 1 and B has to be
- 00:00:36 greater than 1 if we have an algorithm
- 00:00:42 that can be described in the master
- 00:00:45 method recurrence form then there are
- 00:00:47 three rules we need to use to figure out
- 00:00:51 what the asymptotic runtime of that
- 00:00:53 algorithm is all three of these rules
- 00:00:56 will make comparisons of the positive
- 00:01:00 function f of n to the function n to the
- 00:01:05 log base B of A and then some of these
- 00:01:12 rules will include this additional
- 00:01:14 factor of epsilon where epsilon is a
- 00:01:17 constant that is greater than zero so
- 00:01:22 rule number one is the case when F of n
- 00:01:25 is less than n log base B of a minus
- 00:01:29 epsilon for all significantly large ends
- 00:01:32 so in algorithm speak we can say that F
- 00:01:37 of n is equal to o of n log base B of a
- 00:01:42 minus epsilon for this case so this is
- 00:01:45 the case then our recurrence has a
- 00:01:48 runtime that is bounded by theta of n
- 00:01:53 log B of A so why is that well if f of n
- 00:02:00 is o of n log base B of A minus Epsilon
- 00:02:04 then the n log base B of of a is the
- 00:02:09 dominant term so this part of the
- 00:02:11 recurrence is dominant
- 00:02:13 as a result the overall asymptotic
- 00:02:17 runtime is bounded by that term next
- 00:02:22 we'll go over case number two this is
- 00:02:26 the case where ever vent is tightly
- 00:02:28 bounded by n log base B of A and we
- 00:02:33 actually can drop the epsilon term for
- 00:02:34 this then there's one additional factor
- 00:02:37 we have to consider in case two and
- 00:02:39 that's that there is can be a log K of n
- 00:02:45 factor in addition on this F of n term
- 00:02:47 so casein or two happens whenever F of n
- 00:02:52 is tightly bounded so theta bounded by n
- 00:02:55 log base B of A time's a factor of log
- 00:02:58 to the K power of n so in the simplest
- 00:03:03 term this K is equal to zero and this
- 00:03:05 whole term goes to one but it's not
- 00:03:09 always that simple and sometimes we do
- 00:03:10 have an additional law factor of log to
- 00:03:13 some power so this is kind of a more
- 00:03:16 generic way to write it with a log to
- 00:03:18 the K and then so if this is the case
- 00:03:21 then our asymptotic runtime is going to
- 00:03:25 be bounded by theta of n log base B of a
- 00:03:33 times log to the K plus 1 n so it stays
- 00:03:41 the same as like the tight bound except
- 00:03:43 we have an additional factor of log n so
- 00:03:47 all we're doing to get our asymptotic
- 00:03:49 runtime in case number two is we're
- 00:03:51 multiplying by an additional factor of
- 00:03:53 log N to give us a final asymptotic
- 00:03:57 runtime of n to the log base B of a
- 00:04:00 times log to the k plus 1 n so whatever
- 00:04:05 this K was plus one finally we'll cover
- 00:04:08 the last case case number three this is
- 00:04:11 the case where F of n is greater or in
- 00:04:14 asymptotics peak is equal to Omega of n
- 00:04:19 log base B of A plus Epsilon so it's
- 00:04:22 kind of significantly bigger than n log
- 00:04:25 base B of a
- 00:04:27 in this case the F of n term here is the
- 00:04:29 dominant term so our estimate rhotic
- 00:04:32 runtime is going to be bounded and
- 00:04:34 controlled by that dominant term so it's
- 00:04:36 going to be theta of f of n so this is
- 00:04:43 our runtime for case number three
- 00:04:45 however before I finish this so I'm
- 00:04:48 going to write this runtime over here
- 00:04:49 real quick there's one kind of
- 00:04:51 additional factor we need to consider in
- 00:04:53 case number three so our runtime is
- 00:04:55 theta of f of n so the additional thing
- 00:05:00 we have to cover in case number three is
- 00:05:02 that there's a regularity condition so
- 00:05:04 we need to check to make sure that the
- 00:05:05 regularity condition is met before we
- 00:05:08 can use this case so the regularity
- 00:05:12 condition is the following we need to
- 00:05:16 check that that for the values a and the
- 00:05:24 function of n over B so this is from
- 00:05:27 above above that for some value C times
- 00:05:34 f of n this C times F of n term is
- 00:05:38 greater than or equal to that a times f

- 00:05:41 of n over B and in this this see right
- 00:05:47 here is needs to be less than one so if
- 00:05:52 we can find a C that is less than one
- 00:05:54 for some significantly large n and using
- 00:05:58 the values of a and B that are from up
- 00:06:01 above then as long as that's met and it
- 00:06:04 usually is in case three conditions but
- 00:06:06 it's always good to check then we can
- 00:06:09 use case three and say that the
- 00:06:13 recurrence is bounded by f of n so
- 00:06:20 that's about all there is to the master
- 00:06:22 method I'm going to make some future
- 00:06:24 videos that kind of go over some
- 00:06:25 examples using it