Merge Sort, Quick Sort, Binary Search, and Matrix Multiplication MCQs

1. What is the time complexity of Merge Sort in the worst case?

a) O(n) b) O(n log n) c) O(n²) d) O(log n)

2. What is the space complexity of Merge Sort?

a) O(1) b) O(n) c) O(log n) d) O(n²)

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

a) O(n) b) O(n log n) c) O(n²) d) O(log n)

4. What is the best-case time complexity of Quick Sort?

a) O(n) b) O(n log n) c) O(n²) d) O(log n)

5. Which of the following is true about Merge Sort?

a) It is an in-place sorting algorithm. b) It is stable. c) It has a space complexity of O(1). d) It is faster than Quick Sort in all cases.

6. Which of the following is a disadvantage of Quick Sort?

a) It is not stable. b) It has a high space complexity. c) It cannot handle large datasets. d) It is slower than Merge Sort in all cases.

7. What is the time complexity of Binary Search?

a) O(n) b) O(log n) c) O(n log n) d) O(n²)

8. What is a prerequisite for applying Binary Search?

a) The array must be unsorted. b) The array must be sorted. c) The array must contain only positive numbers. d) The array must be of even length.

9. What is the space complexity of Binary Search?

a) O(1) b) O(n) c) O(log n) d) O(n²)

10. Which of the following is true about Binary Search?

a) It can be applied to linked lists. b) It works only on arrays. c) It has a time complexity of O(n). d) It requires additional space proportional to the input size.

11. What is the time complexity of the brute-force multiplication of two n-digit numbers?

a) O(n) b) O(n log n) c) O(n²) d) O(n³)

12. What is the time complexity of Karatsuba's algorithm for multiplying two n-digit numbers?

a) O(n) b) O(n log n) c) O(n^1.585) d) O(n²)

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

a) O(n²) b) O(n^2.807) c) O(n³) d) O(n log n)

14. What is the main idea behind Strassen's Matrix Multiplication?

a) It uses brute-force multiplication. b) It divides the matrices into smaller submatrices. c) It requires O(n²) space. d) It works only on symmetric matrices.

15. What is the space complexity of Strassen's Matrix Multiplication?

a) O(1) b) O(n) c) O(n²) d) O(n³)

Merge Sort, Quick Sort, Binary Search, and Matrix Multiplication MCQs

Your Score: /15