1.1k views
i know time complexity is O(nlogn) but can upper bound given in question consider as TRUE..
asked | 1.1k views
Yes, it is nlogn, bcz we sort them in nlogn. If we not consider the sorting it may take n^2. Or if we take sorting with algo who give complexity of n^2.
Whenever we apply sorting in any problem, we use the best sorting algorithm available. Since merge sort or heap sort take O(nlogn) for best, average and worst case, which is the optimal time among all sorting algorithms, we use merge/heap sort to sort the profits of the objects in fractional knapsack. Hence, time taken will be O(nlogn) in any case. So, O(n^2) is false.

time complexity of fractional knapsack is θ(nlogn)
in worst,best or average case
answered by Veteran (12k points)
for 0/1 knapsack is it O(2^n)
@anjana only if weight is not constant then it can be exponential
@saurabh rai  ...should we consider O(n^2) as correct as it is upper bound of O(nlogn).
^  0/1 knapsack is np-complete problem
@saurab rai

there is no fix upper bound exist for any algorithm
what is fix is tightest upper bound it is best to use nlogn here
but it may also true nbcoz it belongs to class O(nlogn)

@saurabh rai..but made easy gave it as wrong in ALGO Advance test....
ll u plzz post a screenshot f that.... so that is easy 2 understand
In wc- O(n^2)

In avg and best case we can say nlogn
SEE, it can be O(n^2),O(n^3) anything greater than O(nlogn)
BUT we usually consider the tightest upper bound that is O(nlogn)
answered by Junior (959 points)

### First sort according to profit to weight ratio time req : nlogn Then we need one scan to find out max take of profit to weight ratio time needed is: n Overall Time complexity : nlogn + n = O(nlogn)

answered by Active (2.2k points)