13,313 views
3 votes
3 votes
i know time complexity is O(nlogn) but can upper bound given in question consider as TRUE..

3 Answers

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

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)

Related questions

0 votes
0 votes
1 answer
2
LavTheRawkstar asked Apr 15, 2017
3,872 views
Consider the following instance of the knapsack problem: n=3 , W=50 , (v1,v2,v3) = (60,100,120) and weight (w1,w2,w3) = (10,20,30) .solve the given knapsack problem apply...
6 votes
6 votes
2 answers
3