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

Related questions

+3 votes
2 answers
2
asked in Algorithms by Sarvottam Patel Active (1k points)   | 190 views


Top Users Sep 2017
  1. Habibkhan

    6970 Points

  2. Warrior

    2490 Points

  3. Arjun

    2368 Points

  4. rishu_darkshadow

    2136 Points

  5. A_i_$_h

    2004 Points

  6. nikunj

    1980 Points

  7. makhdoom ghaya

    1760 Points

  8. manu00x

    1750 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points


26,060 questions
33,668 answers
79,747 comments
31,079 users