3 votes 3 votes i know time complexity is O(nlogn) but can upper bound given in question consider as TRUE.. Algorithms greedy-algorithm algorithms + – firki lama asked Jan 12, 2017 firki lama 13.3k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply target2017 commented Jan 12, 2017 reply Follow Share 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. 0 votes 0 votes Bongbirdie commented Mar 4, 2017 reply Follow Share 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. 0 votes 0 votes Please log in or register to add a comment.
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) Surabhi Kadur answered Apr 5, 2017 Surabhi Kadur comment Share Follow See all 0 reply Please log in or register to add a comment.
3 votes 3 votes time complexity of fractional knapsack is θ(nlogn) in worst,best or average case saurabh rai answered Jan 12, 2017 saurabh rai comment Share Follow See all 9 Comments See all 9 9 Comments reply Anjana Babu commented Jan 12, 2017 reply Follow Share for 0/1 knapsack is it O(2^n) 1 votes 1 votes sudsho commented Jan 12, 2017 reply Follow Share @anjana only if weight is not constant then it can be exponential 0 votes 0 votes firki lama commented Jan 12, 2017 reply Follow Share @saurabh rai ...should we consider O(n^2) as correct as it is upper bound of O(nlogn). 0 votes 0 votes saurabh rai commented Jan 12, 2017 reply Follow Share ^ 0/1 knapsack is np-complete problem 0 votes 0 votes firki lama commented Jan 12, 2017 reply Follow Share @saurab rai 0 votes 0 votes saurabh rai commented Jan 12, 2017 reply Follow Share 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 n2 bcoz it belongs to class O(nlogn) 0 votes 0 votes firki lama commented Jan 12, 2017 reply Follow Share @saurabh rai..but made easy gave it as wrong in ALGO Advance test.... –1 votes –1 votes saurabh rai commented Jan 12, 2017 reply Follow Share ll u plzz post a screenshot f that.... so that is easy 2 understand 0 votes 0 votes Nitesh Choudhary commented Sep 30, 2017 reply Follow Share In wc- O(n^2) In avg and best case we can say nlogn 0 votes 0 votes Please log in or register to add a comment.
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) aehkn answered Apr 6, 2017 aehkn comment Share Follow See all 0 reply Please log in or register to add a comment.