Coding

# Solving Recurrences Example – Fibonacci (Recursion-Tree Method)

• 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