Coding

Solving Recurrences Example – Binary Search (Master Method)

  • 00:00:00 hi guys in this video I'm going to
  • 00:00:02 quickly go over how to solve the
  • 00:00:04 recurrence for binary search so just a
  • 00:00:07 recap with binary searches let's say
  • 00:00:09 imagine we had a sorted array as we do
  • 00:00:12 right here and we were trying to find
  • 00:00:14 the number 15 in your a binary search
  • 00:00:16 takes the first element which in this
  • 00:00:18 case is 8 and then compares the element
  • 00:00:21 we are looking to looking for which is
  • 00:00:23 15 – 8 15 is larger than 8 so then we're
  • 00:00:26 going to recurse on this side of the
  • 00:00:31 array and we can ignore everything over
  • 00:00:33 here
  • 00:00:34 next we'll select the middle element
  • 00:00:36 again 12 and we see Oh 15 is bigger than
  • 00:00:39 12 so we repeat that process and just
  • 00:00:42 look to the right of it finally we find
  • 00:00:44 15 and that's the number are looking for
  • 00:00:47 so this array did have 15 okay let's all
  • 00:00:51 resolve this and go over the recurrence
  • 00:00:52 and how to solve the runtime of binary
  • 00:00:55 search as I just showed in the previous
  • 00:01:01 example binary search works by taking a
  • 00:01:05 and array let's say of size n and on
  • 00:01:08 each step it looks at the middle element
  • 00:01:11 and then on the next step it only looks
  • 00:01:15 at the side which might contain the
  • 00:01:19 number we are looking for so they're
  • 00:01:21 currents can be described by T of N
  • 00:01:23 equals T of n and then plus o of 1 the o
  • 00:01:27 of 1 is a constant amount of work it
  • 00:01:29 takes to find the middle element so how
  • 00:01:33 do we solve the runtime well this looks
  • 00:01:35 like a perfect use of master method to
  • 00:01:39 me so we have f of n which in this case
  • 00:01:42 is o of 1 so this is our F of n function
  • 00:01:45 and then what is our n log n log base B
  • 00:01:52 of a well we have a base of 2 and an a
  • 00:01:57 which is if we wrote it out as 1 so as
  • 00:02:00 Ray this is our B so this would be n to
  • 00:02:04 the log to 1
  • 00:02:09 which if we simplify that it's just
  • 00:02:12 going to be n to the zero so we simplify
  • 00:02:16 all of that it's just going to be one so
  • 00:02:22 how does ov one compare to one well they
  • 00:02:26 are theta bounded so if F of n function
  • 00:02:30 is Theta bounded by our and log base B
  • 00:02:33 of A this right here ah this right here
  • 00:02:36 so to me this is case two of the master
  • 00:02:40 method case two says that if you have an
  • 00:02:43 F of M that is Theta bounded of your n
  • 00:02:46 log base B of A then to get our runtime
  • 00:02:50 we just multiply it by one factor of log
  • 00:02:53 n so our runtime for binary search would
  • 00:03:01 be O 1 times log n so that is just T of
  • 00:03:07 N equals o 1 times log M which is equal
  • 00:03:13 to o of log n so a little vlog end is
  • 00:03:21 our answer here