Algorithm MCQs

1. What is the primary purpose of the Substitution Method for solving recurrences?

a) To guess the form of the solution and verify it. b) To draw a recursion tree. c) To apply the Master Theorem directly. d) To solve recurrences iteratively.

2. Which of the following is a limitation of the Substitution Method?

a) It cannot handle recurrences with multiple recursive calls. b) It requires an accurate guess of the solution. c) It is only applicable to linear recurrences. d) It cannot handle recurrences with non-constant terms.

3. What is the main idea behind the Recursion-Tree Method?

a) To guess the solution and verify it. b) To visualize the recurrence as a tree and sum the costs at each level. c) To apply the Master Theorem directly. d) To solve recurrences iteratively.

4. Which of the following is true about the Recursion-Tree Method?

a) It is only applicable to divide-and-conquer recurrences. b) It provides an exact solution to the recurrence. c) It is useful for visualizing the cost at each level of recursion. d) It cannot handle recurrences with non-constant terms.

5. What is the Master Theorem used for?

a) To solve linear recurrences. b) To solve divide-and-conquer recurrences of the form \( T(n) = aT(n/b) + f(n) \). c) To solve recurrences with multiple recursive calls. d) To solve recurrences with non-constant terms.

6. Which of the following is NOT a case of the Master Theorem?

a) f(n) = O(n^{log_b a - epsilon}) for some epsilon > 0. b) f(n) = Theta(n^{log_b a}). c) f(n) = Omega(n^{log_b a + epsilon}) for some epsilon > 0. d) f(n) = O(n^{log_b a + epsilon}) for some epsilon > 0.

7. What is the solution to the recurrence T(n) = 2T(n/2) + n using the Master Theorem?

a) T(n) = O(n) b) T(n) = O(nlog n) c)T(n) = O(n^2) d)T(n) = O(log n)

8. What is the solution to the recurrence T(n) = 4T(n/2) + n^2 using the Master Theorem?

a)T(n) = O(n^2) b)T(n) = O(n^2 log n) c)T(n) = O(n^3) d)T(n) = O(n^{log_2 4})

9. Which of the following is true about the Master Theorem?

a) It can solve all types of recurrences. b) It is only applicable to divide-and-conquer recurrences. c) It cannot handle recurrences with non-polynomial \( f(n) \). d) It requires \( f(n) \) to be monotonically increasing.

10. What is the solution to the recurrence T(n) = T(n/2) + 1 using the Master Theorem?

a) T(n) = O(1) b) T(n) = O(log n) c)T(n) = O(n) d) T(n) = O(nlog n)

Recurrence Solving Methods MCQs

Your Score: /10