McqMate

Q. |
## 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? |

A. | o(n) |

B. | o(s) |

C. | o(n2) |

D. | o(s*n) |

Answer» D. o(s*n) | |

Explanation: the time complexity is o(s*n). |

1.4k

0

Do you find this helpful?

9

View all MCQs in

Design and Analysis of AlgorithmsNo comments yet

- Recursion is a method in which the solution of a problem depends on
- In general, which of the following methods isn’t used to find the factorial of a number?
- Which of the following recursive formula can be used to find the factorial of a number?
- Suppose the first fibonnaci number is 0 and the second is 1. What is the sixth fibonnaci number?
- Which of the following is not a fibonnaci number?
- Which of the following recurrence relations can be used to find the nth fibonacci number?
- Which of the following gives the sum of the first n natural numbers?
- If GCD of two number is 8 and LCM is 144, then what is the second number if first number is 72?
- Which of the following is coprime number?
- In terms of Venn Diagram, which of the following expression gives GCD (Given A ꓵ B ≠ Ø)?