Coding

# Recurrence Equations Overview (Computer Science/Algorithms)

• 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