1 00:00:01,510 --> 00:00:06,310 We have written the recursive solution to the Fibonacci question. 2 00:00:06,340 --> 00:00:13,150 Now let's go ahead and discuss the space and time complexity of the approach that we have just now discussed. 3 00:00:13,150 --> 00:00:20,950 And when we come up with the DP solutions to the same question, we will see that we were able to significantly 4 00:00:20,950 --> 00:00:27,910 improve the time complexity and the space complexity as well when we discuss the space optimized tabulation 5 00:00:27,910 --> 00:00:28,480 approach. 6 00:00:28,480 --> 00:00:29,830 So let's get started. 7 00:00:29,830 --> 00:00:36,880 The time complexity of the recursive solution to the Fibonacci question is of the order of two to the 8 00:00:36,880 --> 00:00:37,690 power n. 9 00:00:37,690 --> 00:00:39,040 Now why is that so? 10 00:00:39,040 --> 00:00:43,450 Now first let's just quickly draw the recursion tree over here. 11 00:00:43,450 --> 00:00:44,530 To understand this. 12 00:00:44,530 --> 00:00:47,110 Let's say we want to find f of five. 13 00:00:47,110 --> 00:00:54,850 And we know that for finding f of five, we would have to recursively call f of n minus one and n minus 14 00:00:54,850 --> 00:00:58,450 two, which is f of four and f of three. 15 00:00:58,660 --> 00:01:03,730 Similarly, to find f of four, we would have to call f of three and f of two. 16 00:01:03,730 --> 00:01:08,710 And to find f of three, we would be calling f of two and f of one. 17 00:01:09,500 --> 00:01:14,360 And to find f of three, we would call f of two and f of one. 18 00:01:14,360 --> 00:01:16,460 And that's the same case over here. 19 00:01:16,460 --> 00:01:19,970 For f of two we would have to call f of one and f of zero. 20 00:01:20,270 --> 00:01:22,400 And that's what we have over here as well. 21 00:01:22,400 --> 00:01:28,310 And over here to find f of two we would call f of one and f of zero. 22 00:01:29,520 --> 00:01:31,140 So this is the recursive tree. 23 00:01:31,140 --> 00:01:33,570 And again f of one and f of zero. 24 00:01:33,570 --> 00:01:34,800 We already know the value. 25 00:01:34,800 --> 00:01:38,430 So we would have hit our base case or terminating condition. 26 00:01:38,430 --> 00:01:39,750 And these would return. 27 00:01:40,620 --> 00:01:43,770 So this is how the recursive solution would work. 28 00:01:43,770 --> 00:01:48,420 Notice over here that f of three is computed multiple times. 29 00:01:48,420 --> 00:01:51,420 And that's the case with f of two as well. 30 00:01:51,420 --> 00:01:57,330 But again because we are not storing these values we have to compute them again and again. 31 00:01:57,720 --> 00:02:02,910 So this is the disadvantage of not using dynamic programming or storing these values. 32 00:02:02,910 --> 00:02:05,700 But we'll see more of that in a future video. 33 00:02:06,890 --> 00:02:10,850 Now let's take a look at the time complexity from two angles. 34 00:02:10,850 --> 00:02:16,400 First, we will take a more intuitive approach at finding that the time complexity is of the order of 35 00:02:16,430 --> 00:02:17,570 two to the power n. 36 00:02:17,570 --> 00:02:22,490 And then let's take a look at a mathematical approach to arrive at this time complexity. 37 00:02:22,490 --> 00:02:24,020 So let's get started. 38 00:02:24,020 --> 00:02:30,920 Notice that at each function call, we are calling almost two more function calls. 39 00:02:30,920 --> 00:02:35,480 For example, for f of five we are calling f of four and f of three. 40 00:02:35,480 --> 00:02:38,930 For f of four, we are calling f of three and f of two. 41 00:02:38,930 --> 00:02:41,270 And it goes on in this manner. 42 00:02:41,270 --> 00:02:44,900 So we are doing this almost n times. 43 00:02:44,900 --> 00:02:52,250 And that's why we can say that the time complexity is two into two into two n times. 44 00:02:53,560 --> 00:02:56,740 Which is of the order of two to the power N. 45 00:02:56,770 --> 00:03:03,070 We can also find the time complexity by taking a detailed look at the recursion tree. 46 00:03:03,100 --> 00:03:09,670 Now let's say we want to find f of n, so we would recursively call the same function with the inputs 47 00:03:09,670 --> 00:03:11,770 n minus one and n minus two. 48 00:03:11,800 --> 00:03:18,040 Now this branch would recursively call the same function with the inputs n minus two and n minus three. 49 00:03:18,040 --> 00:03:20,260 And this will keep happening till. 50 00:03:20,260 --> 00:03:22,870 Over here we have n one and zero. 51 00:03:22,870 --> 00:03:27,400 Because our terminating conditions are n is equal to one or n is equal to zero. 52 00:03:27,400 --> 00:03:29,710 So this is the detailed recursion tree. 53 00:03:29,740 --> 00:03:36,760 Now when it comes to identifying the time complexity of a recursive solution, remember we have discussed 54 00:03:36,760 --> 00:03:44,050 previously that we can easily identify this by computing the number of nodes that are there in the recursion 55 00:03:44,050 --> 00:03:44,620 tree. 56 00:03:45,040 --> 00:03:51,160 And then we can just multiply the number of nodes with the work done in each node. 57 00:03:51,160 --> 00:03:57,070 So the time complexity is equal to number of nodes into work done in each node. 58 00:03:57,100 --> 00:04:02,410 Now first let's try to find the number of nodes in this recursive tree. 59 00:04:02,410 --> 00:04:05,020 So over here we have one node. 60 00:04:05,020 --> 00:04:08,710 And then node is over here in this level we have two nodes. 61 00:04:10,270 --> 00:04:13,270 At this level, we have four nodes. 62 00:04:15,070 --> 00:04:16,510 So let's write it down. 63 00:04:16,510 --> 00:04:20,020 So we have one two, four and it goes on in this manner. 64 00:04:20,020 --> 00:04:22,510 In the next level we would have eight nodes. 65 00:04:22,510 --> 00:04:29,350 Now one is nothing but two to the power zero, two is two to the power one, four is two to the power 66 00:04:29,350 --> 00:04:29,740 two. 67 00:04:29,740 --> 00:04:32,410 And it goes on in this pattern. 68 00:04:32,410 --> 00:04:38,230 Now notice over here we had n then n minus one n minus two n minus three. 69 00:04:38,230 --> 00:04:40,660 And it goes on till one. 70 00:04:40,660 --> 00:04:50,050 Now to get one over here we have to do n minus what number or n minus x is equal to one. 71 00:04:50,050 --> 00:04:53,680 If this is the case then x would be n minus one right. 72 00:04:53,680 --> 00:04:57,190 So over here that's n minus n minus one. 73 00:04:57,190 --> 00:05:01,150 Because again n minus n minus one is equal to one. 74 00:05:01,820 --> 00:05:09,680 So when we are doing n minus one, notice that in this level there are two to the power one nodes. 75 00:05:09,680 --> 00:05:13,790 So we had one over here and we have one as the power of two. 76 00:05:13,790 --> 00:05:18,110 Over here we are doing n minus two and the power of two over here was two. 77 00:05:18,140 --> 00:05:25,430 So in this level the maximum number of nodes that will be there will be two to the power. 78 00:05:25,430 --> 00:05:28,640 This value over here which is n minus one. 79 00:05:28,640 --> 00:05:31,310 So we have two to the power zero nodes. 80 00:05:31,310 --> 00:05:33,980 Over here we have two to the power one nodes. 81 00:05:33,980 --> 00:05:38,030 In this level we have two to the power two nodes in this level. 82 00:05:38,030 --> 00:05:45,170 And in the last level, the maximum number of nodes that we can have is two to the power n minus one. 83 00:05:45,170 --> 00:05:51,020 Now I'm saying maximum number of nodes because all these branches will not reach over here. 84 00:05:51,020 --> 00:05:51,470 Again. 85 00:05:51,470 --> 00:05:55,040 We have seen that in the previous case where we drew out f of five. 86 00:05:55,040 --> 00:05:58,820 So you can see that every branch will not reach this level. 87 00:05:58,820 --> 00:06:01,580 But then we are just trying to find the upper bound. 88 00:06:01,580 --> 00:06:07,880 So the maximum number of nodes that can be there in this level are two to the power n minus one. 89 00:06:10,620 --> 00:06:17,310 Now let's just add all of these up together to find the upper bound of the number of nodes, which is 90 00:06:17,310 --> 00:06:23,340 two to the power, zero plus two to the power one, etc. up to two to the power n minus one. 91 00:06:23,370 --> 00:06:29,910 Now this over here is a geometric progression and we are just multiplying with two every time to get 92 00:06:29,910 --> 00:06:30,960 the next term. 93 00:06:30,990 --> 00:06:33,360 Now for a geometric progression. 94 00:06:33,360 --> 00:06:40,680 You must have learned when you were in school that sum up to n terms is equal to a into r to the power 95 00:06:40,680 --> 00:06:47,940 n minus one divided by r minus one, where a is the first term, which in this case is equal to one, 96 00:06:47,940 --> 00:06:53,820 because two to the power, zero is one, and r is the factor that we keep multiplying with, which is 97 00:06:53,820 --> 00:06:54,630 equal to two. 98 00:06:54,660 --> 00:07:00,180 So A is equal to one, r is equal to two, and n is the number of terms. 99 00:07:00,180 --> 00:07:02,880 So we are going from zero to n minus one. 100 00:07:02,880 --> 00:07:05,280 So that's a total of n terms. 101 00:07:08,490 --> 00:07:09,030 All right. 102 00:07:09,030 --> 00:07:13,470 So let's go ahead and put these values into the formula over here. 103 00:07:13,470 --> 00:07:21,450 So you can see that we get s of n is equal to one into two to the power n minus one by two minus one 104 00:07:21,450 --> 00:07:25,200 which simplifies to two to the power n minus one. 105 00:07:25,200 --> 00:07:29,940 So the number of nodes is two to the power n minus one. 106 00:07:29,940 --> 00:07:33,810 Or we can take the upper bound as two to the power n. 107 00:07:34,170 --> 00:07:42,180 Now to find the time complexity, we just need to multiply this with the work done in each node. 108 00:07:42,180 --> 00:07:46,470 So the work done in each node is of the order of one. 109 00:07:46,470 --> 00:07:53,190 Or we are just doing constant time operations in each node, which is just to check whether n is equal 110 00:07:53,190 --> 00:07:54,210 to 0 or 1. 111 00:07:54,210 --> 00:08:01,440 And if not, we just recursively calling the function the same function with lower input, and the recursive 112 00:08:01,440 --> 00:08:05,850 call is already accounted for when we found the number of nodes. 113 00:08:05,850 --> 00:08:09,750 So in each node we are just doing constant time operations. 114 00:08:09,750 --> 00:08:17,010 So that's why the time complexity is of the order of two to the power n into one, or just two to the 115 00:08:17,010 --> 00:08:17,880 power n. 116 00:08:18,650 --> 00:08:25,310 Now, what about the space complexity when it comes to the space complexity, this solution will take 117 00:08:25,310 --> 00:08:27,770 up space of the order of n. 118 00:08:27,770 --> 00:08:29,060 Now why is that so? 119 00:08:29,060 --> 00:08:35,540 Because this is a recursive solution and we will take up space on the recursive call stack. 120 00:08:35,750 --> 00:08:43,100 So notice over here that at any point the maximum depth of the recursion tree is n. 121 00:08:43,100 --> 00:08:50,270 So in this case we had f of five, f of four, f of three, f of two, and f of one, which is five 122 00:08:50,270 --> 00:08:54,050 calls at the same point on the recursive call stack. 123 00:08:54,050 --> 00:09:01,640 So that's why the space complexity of this solution is of the order of n, because on the call stack, 124 00:09:01,640 --> 00:09:07,880 at any given point, we will have at most n function calls at a time. 125 00:09:07,880 --> 00:09:13,760 And again the function over here which is mentioned is the fib function, which we are recursively calling 126 00:09:13,760 --> 00:09:15,830 at each of these instances.