Hey there and welcome back!
In the previous video, we wrote the pseudocode for the approach that we came up with for solving the
fractional knapsack problem.
Let's now take a look at the space and time complexity for this approach.
Now when it comes to the space complexity, it's pretty straightforward that we are not using any auxiliary
space.
And for that reason, the space complexity of this approach is of the order of one or it runs in constant
space.
Now what about the time complexity?
Now, when it comes to the time complexity, let's take a look at what are the aspects in the solution
that we have come up with that take up work?
Okay.
Now over here, notice we have to sort the array on the basis of the profit by weight ratio in reverse
order.
So there are two things we have to find the profit by weight ratio for all the n items in the array.
And then we have to sort the array.
So these two aspects take up work okay.
So finding the profit by weight ratio for n items takes up work of the order of n.
And sorting an array which has n elements takes up work of the order of n log n.
All right.
Now what are the other things that take up work in this solution?
Notice over here we have a for loop where we go through each item in the array.
And because there are n items in the array, this aspect takes up work of the order of n.
So these are the things that take up work in this solution.
And therefore the time complexity of this solution is of the order of n plus n log n plus n.
But because among these three this is the dominating factor.
And therefore we can say that the time complexity of this solution is of the order of n log n.