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.4k 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 Show 6 previous comments 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.