Divide and Conquer

Definitions

1. An algorithmic paradigm that recursively divides a problem into smaller subproblems, solves them independently, and combines the results. Unlike dynamic programming, subproblems don't overlap. Classic examples: merge sort, quicksort, binary search, and the FFT (Fast Fourier Transform). Naturally parallelizable since subproblems are independent.

   In plain English: Solving a big problem by splitting it into smaller independent problems, solving each, and combining the answers.

   Example: "Merge sort is the textbook divide-and-conquer algorithm — split the array in half, sort each half, merge the sorted halves. O(n log n) guaranteed."

Related Terms

• Backtracking
• Data Structure
• Tail Call
• Rolling Update
• Tail Call Optimization
• Operational Transform
• Blue/Green Deployment
• Dijkstra's Algorithm
• Greedy Algorithm