- 00:00:00 hi guys this is Keith galley and in this
- 00:00:02 video I will be quickly going over what
- 00:00:04 a recurrence is in computer science and
- 00:00:08 algorithms to begin I think the CLRS
- 00:00:12 textbook does a good job in defining
- 00:00:15 what a recurrence is so in the textbook
- 00:00:18 it says a recurrence is a describes a
- 00:00:21 function in terms of its value on
- 00:00:23 smaller it just misses class for smaller
- 00:00:27 inputs so the next question you might
- 00:00:31 ask is sure that's what it does but why
- 00:00:34 do we need to do this well sometimes we
- 00:00:38 are given a problem where it's not easy
- 00:00:42 to solve it in like a traditional method
- 00:00:44 so for example if we had a array like 3
- 00:00:49 4 7 9 2 we might be asked to calculate
- 00:00:56 the largest number in that array well
- 00:00:59 that's pretty simple we could scan that
- 00:01:01 entire array one time and find that that
- 00:01:06 biggest number is right here it's the
- 00:01:08 nine however on the other hand we also
- 00:01:12 have problems in computer science such
- 00:01:15 as the Fibonacci like solving for a
- 00:01:20 Fibonacci number right so if you're not
- 00:01:23 familiar a Fibonacci number is kind of a
- 00:01:27 set of numbers that the next number is
- 00:01:31 found by adding together the two
- 00:01:32 previous numbers so using a recurrence
- 00:01:35 we can describe that as T of N equals T
- 00:01:40 of n minus 1 plus T as a terrible T T of
- 00:01:49 n minus 2 and having this recurrence set
- 00:01:54 up we can use methods which I'll
- 00:01:56 describe in later videos on how to
- 00:01:58 calculate the runtime of a equation such
- 00:02:01 as Fibonacci that's not traditionally
- 00:02:03 easy to calculate
- 00:02:05 I'll end this video by providing a
- 00:02:07 couple of the example uses of
- 00:02:09 occurrences in computer science and
- 00:02:11 algorithms
- 00:02:12 so the major set of algorithms that use
- 00:02:17 recurrences are called divide and
- 00:02:22 conquer algorithms
- 00:02:27 there's fixes icon is annoying me and so
- 00:02:32 one of these divide and conquer
- 00:02:34 algorithms you might already be familiar
- 00:02:36 with is merge sort merge sort takes a
- 00:02:41 unsorted array and continuously breaks
- 00:02:45 it up into smaller and smaller arrays
- 00:02:48 sorts those smaller arrays and then
- 00:02:51 works that way works its way back up and
- 00:02:53 combines the small arrays to sorted
- 00:02:56 bigger arrays until you have the final
- 00:03:00 entire sorted array we can describe this
- 00:03:04 with a recurrence as follows so you have
- 00:03:08 T of N equals 2 T of n over 2 plus o of
- 00:03:20 n so what does this all mean so it's
- 00:03:24 saying we have an array of size n we
- 00:03:27 split that array into two arrays of size
- 00:03:30 n over 2 and then finally once we have
- 00:03:35 these two sorted smaller arrays we
- 00:03:39 combine them to make the sorted large
- 00:03:41 array any final step that takes o of n
- 00:03:44 time using methods that I'll explain in
- 00:03:49 following videos you can get the run
- 00:03:51 time for merge sort
- 00:03:54 one final example of another you know
- 00:03:58 example of a recurrence would be
- 00:04:06 binary search so binary search takes a
- 00:04:12 sorted array so we can make a sorted
- 00:04:15 array real quick so a sorted array so
- 00:04:23 let's say 1 3 5 6 9 10 11 and let's say
- 00:04:31 I wanted to find if 11 is in this sorted
- 00:04:35 array and I didn't know anything about
- 00:04:37 it
- 00:04:37 well binary search why works by taking
- 00:04:40 the first element which was 6 and then
- 00:04:43 checking to see if the number we're
- 00:04:44 looking for which is 11 is bigger or
- 00:04:47 smaller than 6 and then just looking
- 00:04:49 recursively at the side that it is on
- 00:04:53 comparing to 6 so in this case 11 is
- 00:04:56 bigger so we can ignore all this stuff
- 00:04:58 in the 6th and back next we'd repeat the
- 00:05:02 process and find 10 know that 11 is
- 00:05:05 bigger and eliminate all of this and
- 00:05:07 finally we check this last value we see
- 00:05:10 that it matches up to 11 and we know
- 00:05:13 that the array does in fact contain the
- 00:05:15 11 so what is the recurrence equation
- 00:05:17 for binary search well it can be
- 00:05:21 subscribed as T of N equals T of n over
- 00:05:27 2 plus o of 1 so what this means is we
- 00:05:34 have an initial array on each step we
- 00:05:37 only look at half of the array so like
- 00:05:41 after I found the middle element I knew
- 00:05:43 I only had to look either to the
- 00:05:45 elements before it or after it
- 00:05:47 and finally the O of 1 just shows the
- 00:05:51 time it takes to get that middle element
- 00:05:53 so this is the recurrence equation for
- 00:05:56 binary search and once again it can be
- 00:05:58 solved in future methods that I'll post
- 00:06:01 as videos of this channel thank you for
- 00:06:04 watching and if you have any feedback
- 00:06:06 please let me know and leave a comment
- 00:06:09 on this video
