GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
462 views
i know time complexity is O(nlogn) but can upper bound given in question consider as TRUE..
asked in Algorithms by Junior (927 points)   | 462 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.

3 Answers

+1 vote
time complexity of fractional knapsack is θ(nlogn)
in worst,best or average case
answered by Veteran (10.8k 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
0 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)
answered by (393 points)  
0 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)

answered by Active (1.1k points)  

Related questions

+2 votes
2 answers
2
asked in Algorithms by Sarvottam Patel Junior (959 points)   | 135 views


Top Users Jul 2017
  1. Bikram

    5784 Points

  2. manu00x

    3602 Points

  3. Arjun

    1988 Points

  4. Debashish Deka

    1924 Points

  5. joshi_nitish

    1908 Points

  6. pawan kumarln

    1680 Points

  7. Tesla!

    1426 Points

  8. Hemant Parihar

    1334 Points

  9. Shubhanshu

    1180 Points

  10. Arnab Bhadra

    1124 Points


24,169 questions
31,187 answers
71,040 comments
29,512 users