McqMate

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. |

1.1k

0

Do you find this helpful?

11

View all MCQs in

Design and Analysis of AlgorithmsNo comments yet

- 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