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