- 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