Coding

# Master Method to Solve Recurrences – Overview

• 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