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