Coding

Solving Recurrences Example – Fibonacci (Recursion-Tree Method)

2 years ago
  • 00:00:00 hi guys in this video I'm going to show
  • 00:00:02 you how to calculate the run time to
  • 00:00:04 find the nth Fibonacci number using the
  • 00:00:07 recursion tree method so the fibonacci
  • 00:00:12 sequence is defined as T of n equals T
  • 00:00:15 of n minus 1 plus T of n minus 2
  • 00:00:22 and then also just noting that our first
  • 00:00:25 and second numbers are 0 and 1 ok so we
  • 00:00:28 have this recurrence well if you are
  • 00:00:32 familiar with the master method you'll
  • 00:00:33 kind of notice right away that this
  • 00:00:37 recurrence right here does not match the
  • 00:00:39 form we need to use the master method so
  • 00:00:42 we'll have to do it in some other way
  • 00:00:45 all right
  • 00:00:46 how are we going to do that well to
  • 00:00:50 calculate the nth Fibonacci number so we
  • 00:00:54 have n right here we need to know the N
  • 00:00:57 minus 1 Fibonacci number and the N minus
  • 00:01:00 2 Fibonacci number to calculate the n
  • 00:01:03 minus first Fibonacci number we need to
  • 00:01:06 know the N minus 2 Fibonacci number and
  • 00:01:09 the N minus 3 so nachi number similarly
  • 00:01:13 for n minus 2 we need the n minus third
  • 00:01:15 Fibonacci number and the N minus 4 Nachi
  • 00:01:19 number now in this process is going to
  • 00:01:23 keep repeating we're going to need you
  • 00:01:26 know two Fibonacci numbers for each like
  • 00:01:30 step in our algorithm until we get to
  • 00:01:35 our base cases which is like T of 0 or T
  • 00:01:41 of 1 whatever going to say I guess we'll
  • 00:01:43 decide T 1 and T of 2 T of 1 which is 0
  • 00:01:46 and T of 2 which is 1 so we're working
  • 00:01:50 our way down here until we get to these
  • 00:01:54 base cases ok so I think the key thing
  • 00:01:58 to note here is how many levels are we
  • 00:02:02 going down well if we start with n and
  • 00:02:05 we decrease n by 1 each time then in the
  • 00:02:10 worst case when we're not like looking
  • 00:02:12 at it maybe is minus 2 times
  • 00:02:14 it's going to take us n levels to get
  • 00:02:17 down all the way to the bottom where
  • 00:02:19 we're at kind of 1 or 2 or 0 about n so
  • 00:02:23 I mean it may be a little off but don't
  • 00:02:25 worry about that for the sake of this
  • 00:02:26 problem so we have n right here next I
  • 00:02:30 want to know is you know when we get to
  • 00:02:33 the bottom how many leaf nodes will we
  • 00:02:34 have to add together so if T of n is
  • 00:02:37 equal to T of n minus 1 plus T of n
  • 00:02:42 minus 2 if we get all the way to the
  • 00:02:45 bottom here how many things do we have
  • 00:02:47 to add together well I can kind of see a
  • 00:02:51 pattern here if we start to the top well
  • 00:02:52 we have one term in the first level we
  • 00:02:55 have two terms in the second four terms
  • 00:02:58 here and as you can see we are branching
  • 00:03:01 factor of two for each one of these
  • 00:03:02 things so when we get all the way to the
  • 00:03:04 bottom here we go down and levels I know
  • 00:03:09 that it is going to be two to the end
  • 00:03:12 leaf nodes so if we have to the end leaf
  • 00:03:16 nodes and our kind of final step of
  • 00:03:18 calculating this value of n right here
  • 00:03:20 value of n it's just adding like our
  • 00:03:25 leaf nodes together and that's in
  • 00:03:27 constant function that I'm saying that
  • 00:03:29 our run time is o of two to the N for
  • 00:03:33 Fibonacci calculating the nth Fibonacci
  • 00:03:36 number so one thing you might be
  • 00:03:39 wondering is o over the to the N well
  • 00:03:41 yeah that's just calculating the leaf
  • 00:03:42 nodes what about every other node well
  • 00:03:44 kind of my argument saying that like we
  • 00:03:47 don't really care is the level of the n
  • 00:03:49 minus first level so if we only went
  • 00:03:51 down like n minus 1 levels well that
  • 00:03:54 would have half as many nodes as this
  • 00:03:57 end level does and when we talk about
  • 00:04:01 asymptotic notation we don't care about
  • 00:04:05 like additional factors as long as it's
  • 00:04:07 within a constant factor so like because
  • 00:04:11 we've 2 to the N here we don't care
  • 00:04:13 about the 2 to the N minus 1 additional
  • 00:04:15 things because it's you know less than a
  • 00:04:17 constant of two times this value here so
  • 00:04:22 our final runtime for this algorithm is
  • 00:04:24 o to the 2 to the N
  • 00:04:27 so that is the runtime to calculate the
  • 00:04:30 enthalpy number thank you for watching

You may also like