Q. Which of the following implementations of Catalan numbers has the smallest time complexity?

(A) dynamic programming
(B) binomial coefficients
(C) recursion
(D) all have equal time complexity

💬 Discuss

✅ Correct Answer: (B) binomial coefficients

Explanation: The time complexities are as follows:
Dynamic programming: O(n2) Recursion: Exponential Binomial coefficients: O(n).

Published by Mr. Dubey ⭐ 104.82K Points at 16-Sep-2023 03:44 pm in Design and Analysis of Algorithms

Explanation by: Mr. Dubey

The time complexities are as follows:
Dynamic programming: O(n2) Recursion: Exponential Binomial coefficients: O(n).

💬 Discussion

📊 Question Analytics

👁️

198

Total Visits

📽️

3 y ago

Published

🎖️

Mr. Dubey

Publisher

📈

92%

Success Rate