49. What is divide and conquer? Give three examples.
MediumDivide & conquer
Technical
Show model answer
Divide the problem into smaller independent subproblems, solve them recursively, and combine the results. Examples: merge sort, quicksort, binary search, fast exponentiation, counting inversions, closest pair of points (O(n log n)), Karatsuba multiplication and Strassen's matrix multiplication.
It differs from dynamic programming because the subproblems do not overlap.