The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
1.1k views
i know time complexity is O(nlogn) but can upper bound given in question consider as TRUE..
asked in Algorithms by Active (1.1k points) | 1.1k 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

+2 votes
time complexity of fractional knapsack is θ(nlogn)
in worst,best or average case
answered by Veteran (12k 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
In wc- O(n^2)

In avg and best case we can say nlogn
+2 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 Junior (959 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 (2.2k points)

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

28,831 questions
36,676 answers
90,577 comments
34,638 users