72 views
i know time complexity is O(nlogn) but can upper bound given in question consider as TRUE..
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.

time complexity of fractional knapsack is θ(nlogn)
in worst,best or average case
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