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

1 Answer

0 votes
time complexity of fractional knapsack is θ(nlogn)
in worst,best or average case
answered by Boss (9.5k 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

Related questions

0 votes
0 answers
2
asked ago in Algorithms by Sarvottam Patel Junior (889 points)   | 10 views
0 votes
0 answers
3
asked in Algorithms by Tushar Shinde Loyal (2.5k points)   | 182 views
Top Users Jan 2017
  1. Debashish Deka

    9660 Points

  2. sudsho

    5554 Points

  3. Bikram

    5270 Points

  4. Habibkhan

    4878 Points

  5. Vijay Thakur

    4498 Points

  6. Arjun

    4418 Points

  7. saurabh rai

    4236 Points

  8. Sushant Gokhale

    4140 Points

  9. Kapil

    3848 Points

  10. santhoshdevulapally

    3808 Points

Monthly Topper: Rs. 500 gift card

19,443 questions
24,221 answers
53,870 comments
20,372 users