Divide and Conquer definition
Divide and conquer solves a problem by splitting it into smaller subproblems, solving those, and using their results.
Divide and Conquer in a picture
How it works
A small enough subproblem is handled directly. For larger inputs, divide them into smaller parts and apply the same strategy. Some methods combine all partial results, while a search can discard parts that cannot contain the answer.
Worked examples
What is a natural base case for finding a maximum in a nonempty list?
A list with one item, whose maximum is that item.
How does binary search use divide and conquer?
It splits the possible range and solves only the half that can contain the target.
How can a recursive sorting method combine two sorted halves?
Merge them by repeatedly taking the smaller front item.
Common mistake
Make the subproblems smaller and explain how their solutions produce a solution to the original problem.
Quick check
Why include a base case?
Show answer
It tells you when to stop dividing and solve directly.
Can two subproblems have different sizes?
Show answer
Yes, the sizes depend on the method.
Sources
Flashcard
Divide and Conquer
Reveal the definition
Divide and conquer solves a problem by splitting it into smaller subproblems, solving those, and using their results.
Effortless Math. “Divide and Conquer.” Math Dictionary.
