[Solved] Time complexity of fractional knapsack problem is

Computer Science Engineering (CSE)
Design and Analysis of Algorithms
Time complexity of fractional knapsack p...

Q.	Time complexity of fractional knapsack problem is
A.	o(n log n)
B.	o(n)
C.	o(n2)
D.	o(nw)
Answer» A. o(n log n)
Explanation: as the main time taking a step is of sorting so it defines the time complexity of our code. so the time complexity will be o(n log n) if we use quick sort for sorting.

View all MCQs in: Design and Analysis of Algorithms

Discussion

Related Questions

Which of the following statement about 0/1 knapsack and fractional knapsack problem is correct?
The result of the fractional knapsack is greater than or equal to 0/1 knapsack.
Fractional knapsack problem can be solved in time O(n).
The main time taking step in fractional knapsack problem is
Fractional knapsack problem is also known as
Fractional knapsack problem is solved most efficiently by which of the following algorithm?
You are given infinite coins of N denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. What is the time complexity of a dynamic programming implementation used to solve the coin change problem?
Recursive solution of subset sum problem is faster than dynamic problem solution in terms of time complexity.
Recursive solution of Set partition problem is faster than dynamic problem solution in terms of time complexity.
The Knapsack problem is an example of