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
  • 00:06:06 please let me know and leave a comment
  • 00:06:09 on this video