1
00:00:00,170 --> 00:00:02,060
Hey there and welcome back!

2
00:00:02,090 --> 00:00:08,630
In the previous video, we wrote the pseudocode for the approach that we came up with for solving the

3
00:00:08,630 --> 00:00:10,520
fractional knapsack problem.

4
00:00:10,550 --> 00:00:15,230
Let's now take a look at the space and time complexity for this approach.

5
00:00:15,260 --> 00:00:21,980
Now when it comes to the space complexity, it's pretty straightforward that we are not using any auxiliary

6
00:00:21,980 --> 00:00:22,580
space.

7
00:00:22,580 --> 00:00:28,940
And for that reason, the space complexity of this approach is of the order of one or it runs in constant

8
00:00:28,940 --> 00:00:29,600
space.

9
00:00:29,630 --> 00:00:31,850
Now what about the time complexity?

10
00:00:31,880 --> 00:00:38,840
Now, when it comes to the time complexity, let's take a look at what are the aspects in the solution

11
00:00:38,840 --> 00:00:41,510
that we have come up with that take up work?

12
00:00:41,510 --> 00:00:41,900
Okay.

13
00:00:41,900 --> 00:00:49,340
Now over here, notice we have to sort the array on the basis of the profit by weight ratio in reverse

14
00:00:49,340 --> 00:00:49,790
order.

15
00:00:49,790 --> 00:00:56,300
So there are two things we have to find the profit by weight ratio for all the n items in the array.

16
00:00:56,300 --> 00:00:58,610
And then we have to sort the array.

17
00:00:58,610 --> 00:01:01,760
So these two aspects take up work okay.

18
00:01:01,760 --> 00:01:07,850
So finding the profit by weight ratio for n items takes up work of the order of n.

19
00:01:07,850 --> 00:01:14,060
And sorting an array which has n elements takes up work of the order of n log n.

20
00:01:14,060 --> 00:01:14,630
All right.

21
00:01:14,630 --> 00:01:17,750
Now what are the other things that take up work in this solution?

22
00:01:17,750 --> 00:01:22,910
Notice over here we have a for loop where we go through each item in the array.

23
00:01:22,910 --> 00:01:29,000
And because there are n items in the array, this aspect takes up work of the order of n.

24
00:01:29,000 --> 00:01:32,780
So these are the things that take up work in this solution.

25
00:01:32,780 --> 00:01:41,330
And therefore the time complexity of this solution is of the order of n plus n log n plus n.

26
00:01:41,330 --> 00:01:45,020
But because among these three this is the dominating factor.

27
00:01:45,020 --> 00:01:50,840
And therefore we can say that the time complexity of this solution is of the order of n log n.