Divide and Conquer Algorithm MCQs
Basic Divide and Conquer Concepts (30 Questions)
1. What is the fundamental principle of Divide and Conquer?
A) Break problem into smaller subproblems
B) Solve subproblems recursively
C) Combine solutions of subproblems
D) All of the above
Answer: D) All of the above
Divide and Conquer involves dividing the problem, solving subproblems, and combining solutions.
2. Which of these is NOT a Divide and Conquer algorithm?
A) Merge Sort
B) Quick Sort
C) Binary Search
D) Bubble Sort
Answer: D) Bubble Sort
Bubble Sort is an iterative algorithm, not Divide and Conquer.
3. What is the time complexity of Merge Sort?
A) O(n)
B) O(n log n)
C) O(n²)
D) O(log n)
Answer: B) O(n log n)
Merge Sort divides the array in halves (log n) and merges in linear time (n).
4. What is the base case in a recursive Divide and Conquer algorithm?
A) When the problem is small enough to solve directly
B) When the array is sorted
C) When the problem is divided into two parts
D) When the recursion depth exceeds a limit
Answer: A) When the problem is small enough to solve directly
Base case stops the recursion when problem size is trivial.
5. Which part of Quick Sort implements the Divide step?
A) Merging sorted subarrays
B) Partitioning the array
C) Selecting the pivot
D) Both B and C
Answer: D) Both B and C
Partitioning divides the array based on the pivot element.
6. What is the worst-case time complexity of Quick Sort?
A) O(n log n)
B) O(n²)
C) O(log n)
D) O(n)
Answer: B) O(n²)
Worst case occurs when pivot is always smallest or largest element.
7. In Binary Search, how is the problem divided in each step?
A) Into two equal halves
B) Into three parts
C) By comparing with first element
D) By comparing with middle element
Answer: D) By comparing with middle element
Binary Search compares with middle element to decide which half to search.
8. What is the time complexity of Binary Search?
A) O(n)
B) O(n log n)
C) O(log n)
D) O(1)
Answer: C) O(log n)
Each comparison halves the search space.
9. Which algorithm finds the maximum subarray sum using Divide and Conquer?
A) Kadane's Algorithm
B) Merge Sort
C) Quick Sort
D) Maximum Subarray Algorithm
Answer: D) Maximum Subarray Algorithm
This algorithm divides the array and finds max sums in left, right, and crossing subarrays.
10. What is the recurrence relation for Merge Sort?
A) T(n) = T(n/2) + O(n)
B) T(n) = 2T(n/2) + O(n)
C) T(n) = T(n-1) + O(n)
D) T(n) = T(n/2) + O(1)
Answer: B) T(n) = 2T(n/2) + O(n)
Merge Sort divides into 2 subproblems of size n/2 and merges in O(n) time.
11. What is the space complexity of standard Merge Sort implementation?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Answer: C) O(n)
Merge Sort requires auxiliary space for merging.
12. Which algorithm uses the "partition" step as its divide step?
A) Merge Sort
B) Quick Sort
C) Binary Search
D) Strassen's Algorithm
Answer: B) Quick Sort
Quick Sort partitions the array around a pivot element.
13. What is the best-case time complexity of Quick Sort?
A) O(n log n)
B) O(n²)
C) O(log n)
D) O(n)
Answer: A) O(n log n)
Best case occurs when pivot divides array into equal parts.
14. Which algorithm multiplies two matrices in O(n^2.81) time using Divide and Conquer?
A) Standard Matrix Multiplication
B) Strassen's Algorithm
C) Coppersmith-Winograd Algorithm
D) Karatsuba Algorithm
Answer: B) Strassen's Algorithm
Strassen's reduces the number of multiplications needed.
15. What is the recurrence relation for Binary Search?
A) T(n) = T(n/2) + O(n)
B) T(n) = 2T(n/2) + O(1)
C) T(n) = T(n-1) + O(1)
D) T(n) = T(n/2) + O(1)
Answer: D) T(n) = T(n/2) + O(1)
Binary Search divides problem in half and does constant work.
16. Which of these is an advantage of Divide and Conquer?
A) Often leads to efficient algorithms
B) Naturally suited for parallel processing
C) Can reduce time complexity significantly
D) All of the above
Answer: D) All of the above
Divide and Conquer offers all these advantages.
17. What is the time complexity of Strassen's Matrix Multiplication?
A) O(n²)
B) O(n³)
C) O(n^2.81)
D) O(n log n)
Answer: C) O(n^2.81)
Strassen's is faster than standard O(n³) matrix multiplication.
18. Which algorithm uses the "conquer" step before the "divide" step?
A) Merge Sort
B) Quick Sort
C) Binary Search
D) None of the above
Answer: D) None of the above
All standard Divide and Conquer algorithms divide first.
19. What is the space complexity of Quick Sort?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Answer: B) O(log n)
Quick Sort uses O(log n) space for recursion stack in average case.
20. Which algorithm is NOT typically implemented recursively?
A) Merge Sort
B) Quick Sort
C) Binary Search
D) Bubble Sort
Answer: D) Bubble Sort
Bubble Sort is typically implemented iteratively.
21. What is the main disadvantage of Divide and Conquer algorithms?
A) Recursion overhead
B) Difficult to implement
C) Not suitable for small inputs
D) All of the above
Answer: A) Recursion overhead
Recursion can lead to stack overhead and isn't always optimal for small problems.
22. Which algorithm finds the closest pair of points using Divide and Conquer?
A) Merge Sort
B) Quick Sort
C) Closest Pair Algorithm
D) Binary Search
Answer: C) Closest Pair Algorithm
This algorithm divides points and checks strip of points near division.
23. What is the time complexity of the closest pair algorithm?
A) O(n²)
B) O(n log n)
C) O(log n)
D) O(n)
Answer: B) O(n log n)
The algorithm divides points and combines results efficiently.
24. Which algorithm uses Divide and Conquer to compute power(x, n)?
A) Linear multiplication
B) Exponentiation by squaring
C) Binary exponentiation
D) Both B and C
Answer: D) Both B and C
These are names for the same Divide and Conquer approach.
25. What is the time complexity of exponentiation by squaring?
A) O(n)
B) O(log n)
C) O(n log n)
D) O(1)
Answer: B) O(log n)
Each recursive step halves the exponent.
26. Which algorithm multiplies large numbers faster than standard multiplication?
A) Karatsuba Algorithm
B) Strassen's Algorithm
C) Merge Sort
D) Binary Search
Answer: A) Karatsuba Algorithm
Karatsuba reduces multiplication to three half-size multiplications.
27. What is the time complexity of Karatsuba multiplication?
A) O(n²)
B) O(n^1.585)
C) O(n log n)
D) O(n)
Answer: B) O(n^1.585)
Faster than standard O(n²) multiplication.
28. Which problem can be solved using Divide and Conquer for convex hull?
A) Quickhull
B) Graham Scan
C) Jarvis March
D) All of the above
Answer: A) Quickhull
Quickhull uses Divide and Conquer approach.
29. What is the average case time complexity of Quick Sort?
A) O(n log n)
B) O(n²)
C) O(log n)
D) O(n)
Answer: A) O(n log n)
Average case is same as Merge Sort.
30. Which algorithm is more cache-efficient: Merge Sort or Quick Sort?
A) Merge Sort
B) Quick Sort
C) Both are equal
D) Depends on implementation
Answer: B) Quick Sort
Quick Sort has better locality of reference.
Advanced Divide and Conquer (20 Questions)
1. What is the Master Theorem used for?
A) Solving recurrence relations
B) Matrix multiplication
C) Sorting algorithms
D) Graph traversal
Answer: A) Solving recurrence relations
Master Theorem provides solution to common Divide and Conquer recurrences.
2. Which case of Master Theorem applies to Merge Sort?
A) Case 1
B) Case 2
C) Case 3
D) None of the above
Answer: B) Case 2
Merge Sort's work is evenly distributed (f(n) = Θ(n log n)).
3. What is the recurrence relation for Strassen's Matrix Multiplication?
A) T(n) = 7T(n/2) + O(n²)
B) T(n) = 8T(n/2) + O(n²)
C) T(n) = 7T(n/2) + O(n)
D) T(n) = 8T(n/2) + O(n)
Answer: A) T(n) = 7T(n/2) + O(n²)
Strassen's uses 7 multiplications of half-size matrices.
4. Which algorithm solves the selection problem (finding kth smallest) in O(n) average time?
A) Quickselect
B) Merge Sort
C) Binary Search
D) Heap Sort
Answer: A) Quickselect
Quickselect is a Divide and Conquer algorithm derived from Quick Sort.
5. What is the worst-case time complexity of Quickselect?
A) O(n)
B) O(n log n)
C) O(n²)
D) O(log n)
Answer: C) O(n²)
Worst case occurs with bad pivot selection, similar to Quick Sort.
6. Which algorithm finds the median of medians for better pivot selection?
A) Median of Medians
B) Quick Sort
C) Merge Sort
D) Binary Search
Answer: A) Median of Medians
This algorithm guarantees good pivots for O(n) worst-case selection.
7. What is the time complexity of the Median of Medians algorithm?
A) O(n)
B) O(n log n)
C) O(n²)
D) O(log n)
Answer: A) O(n)
It finds an approximate median in linear time.
8. Which algorithm uses Divide and Conquer to compute Fibonacci numbers?
A) Naive recursive
B) Matrix exponentiation
C) Dynamic programming
D) All of the above
Answer: B) Matrix exponentiation
Matrix exponentiation uses Divide and Conquer for O(log n) Fibonacci.
9. What is the time complexity of the fastest Divide and Conquer Fibonacci algorithm?
A) O(n)
B) O(2^n)
C) O(log n)
D) O(1)
Answer: C) O(log n)
Matrix exponentiation approach achieves logarithmic time.
10. Which algorithm uses Divide and Conquer for polynomial multiplication?
A) Karatsuba
B) Strassen
C) Fast Fourier Transform
D) Both A and C
Answer: D) Both A and C
Both Karatsuba and FFT use Divide and Conquer for polynomials.
11. What is the time complexity of FFT-based polynomial multiplication?
A) O(n²)
B) O(n log n)
C) O(n)
D) O(log n)
Answer: B) O(n log n)
FFT achieves n log n time for polynomial multiplication.
12. Which algorithm uses Divide and Conquer for order statistics?
A) Quickselect
B) Median of Medians
C) Both A and B
D) None of the above
Answer: C) Both A and B
Both are Divide and Conquer approaches for order statistics.
13. What is the space complexity of in-place Quick Sort?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
Answer: B) O(log n)
Due to recursion stack depth in balanced cases.
14. Which optimization can improve Quick Sort's performance on small subarrays?
A) Switch to Insertion Sort
B) Use median-of-three pivot
C) Both A and B
D) None of the above
Answer: C) Both A and B
Both are common optimizations for Quick Sort.
15. What is the main advantage of Merge Sort over Quick Sort?
A) Better cache performance
B) Stable sorting
C) Guaranteed O(n log n) time
D) Both B and C
Answer: D) Both B and C
Merge Sort is stable and has guaranteed performance.
16. Which algorithm is preferred for sorting linked lists?
A) Quick Sort
B) Merge Sort
C) Heap Sort
D) Insertion Sort
Answer: B) Merge Sort
Merge Sort is well-suited for linked lists due to sequential access.
17. What is the time complexity of the fastest known matrix multiplication algorithm?
A) O(n²)
B) O(n^2.81)
C) O(n^2.372)
D) O(n log n)
Answer: C) O(n^2.372)
Coppersmith-Winograd and subsequent improvements achieve this.
18. Which problem can be solved using Divide and Conquer for counting inversions?
A) Modified Merge Sort
B) Quick Sort
C) Binary Search
D) None of the above
Answer: A) Modified Merge Sort
Merge Sort can be modified to count inversions during merge step.
19. What is the time complexity of counting inversions using modified Merge Sort?
A) O(n²)
B) O(n log n)
C) O(n)
D) O(log n)
Answer: B) O(n log n)
Same as Merge Sort with additional constant work during merge.
20. Which algorithm uses Divide and Conquer for solving recurrence relations?
A) Master Theorem
B) Recursion Tree Method
C) Substitution Method
D) All of the above
Answer: D) All of the above
All these methods analyze Divide and Conquer recurrences.
Related Algorithm Resources