Algorithm MCQs

1. What is the time complexity of MergeSort?

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

2. Which of the following is NOT a divide-and-conquer algorithm?

a) MergeSort b) QuickSort c) Binary Search d) Bubble Sort

3. What is the worst-case time complexity of QuickSort?

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

4. What is the time complexity of Binary Search?

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

5. What is the recurrence relation for MergeSort?

a)T(n) = 2T(n/2) + O(n) b)T(n) = T(n-1) + O(n) c)T(n) = T(n/2) + O(n) d)T(n) = 2T(n-1) + O(n)

6. What is the time complexity of Strassen's Matrix Multiplication?

a)O(n^3) b)O(n^{2.807}) c)O(n^2) d)O(nlog n)

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

a) It solves recurrence relations of the form T(n) = aT(n/b) + f(n) . b) It only applies to divide-and-conquer algorithms. c) It provides the time complexity of recursive algorithms. d) All of the above.

8. What is the time complexity of the closest pair problem using divide-and-conquer?

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

9. What is the space complexity of MergeSort?

a)O(1) b)O(n) c)O(log n) d)O(n^2)

10. Which of the following is a key advantage of QuickSort over MergeSort?

a) It has a better worst-case time complexity. b) It is an in-place sorting algorithm. c) It is stable. d) It requires less space.

11. What is the time complexity of the multiplication of large integers using the divide-and-conquer approach?

a)O(n^2) b)O(n^{1.585}) c)O(nlog n) d)O(n)

12. Which of the following is a divide-and-conquer algorithm for matrix multiplication?

a) Strassen's Algorithm b) Bubble Sort c) Insertion Sort d) Selection Sort

13. What is the time complexity of the Master Theorem for T(n) = 4T(n/2) + n^2 ?

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

14. What is the time complexity of the Master Theorem for T(n) = 2T(n/2) + n ?

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

15. What is the time complexity of the Master Theorem for T(n) = 8T(n/2) + n^3 ?

a)O(n^3) b)O(n^3log n) c)O(n^4) d)O(n^2)

16. What is the time complexity of the Master Theorem for T(n) = T(n/2) + 1 ?

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

17. Which of the following is a disadvantage of Strassen's Matrix Multiplication?

a) It has a higher constant factor. b) It is not stable. c) It requires additional space. d) All of the above.

18. What is the time complexity of the Master Theorem for T(n) = 7T(n/2) + n^2 ?

a)O(n^{log_2 7}) b)O(n^2) c)O(n^2 log n) d)O(n^3)

19. What is the time complexity of the Master Theorem for T(n) = T(n/2) + n ?

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

20. Which of the following is a divide-and-conquer algorithm for sorting?

a) MergeSort b) QuickSort c) Both a and b d) None of the above

Divide-and-Conquer Algorithms MCQs

Your Score: /20