Divide and Conquer as a Design Method
Split the input, solve the pieces the same way, and spend the remaining effort combining. Seen as a method rather than as one sorting trick, it produces fast multiplication, closest-pair search, and selection without sorting.
What a learner can do afterwards
- Design a divide and conquer solution to a problem the learner has not seen solved that way
- Say where the work sits for a given split: mostly in the split, the combine, or the leaves
- Explain why splitting into pieces of unequal size can still pay off
1 · Read
Divide and conquer is a design method with three moves. Split the input into smaller pieces, solve each piece the same way, then combine the answers. The recursion stops on pieces so small you solve them directly. Split into two, split every piece again, and you hold four pieces.
Selection without sorting shows the shape. Split the input, keep only the piece that holds the answer, and solve that piece the same way. The skipped piece is work you never do.
For any split, ask where the work sits. It can sit mostly in the split, mostly in the combine, or down in the leaves. If splitting is free and combining scans the pieces, the combine dominates.
Unequal pieces can still pay off. If one piece holds almost all the input, you still shrink the problem every round. Judge a split by its total cost, not by its symmetry.
Split the input, solve the pieces the same way, combine the answers, and judge each split by where the work sits.
More to read
Divide and conquer algorithms
Some ways of sorting an array are slow. Selection sort and insertion sort can take about n squared steps on a list of n items, so a big list takes a very long time.
Divide and conquer gives a better plan. Instead of attacking the whole list at once, you split the problem into smaller pieces, solve each piece the same way, and then combine the answers. Recursion does the heavy lifting: each smaller piece gets the same treatment until the pieces are tiny and trivial.
Merge sort is a classic example. Cut the list in half, sort each half with merge sort, and then merge the two sorted halves into one sorted list. Quicksort picks a pivot, moves smaller items to one side and larger ones to the other, then sorts each side the same way.
Where does the work sit? In merge sort, most of the effort is in the combine step, the merging of sorted halves. In quicksort, most of the effort is in the split step, the partitioning around the pivot. Both run far faster than n squared on typical inputs, which is why divide and conquer shows up again and again in algorithm design. Unequal splits can still pay off. Quicksort rarely cuts exactly in half, yet with decent pivots the average depth stays near log n, so the total stays near n log n. Selection pushes this further: partition around a pivot, then recurse into only the side holding the kth item, finding it without sorting the rest.
Algorithmic Paradigms
When you face a new computing problem, you do not have to invent a solution from scratch. Designers have collected patterns, called algorithmic paradigms, that solve whole families of problems.
Divide and conquer is one of these patterns. You break the input into pieces, solve each piece with the same method, and combine the results. It works when a problem splits cleanly and the pieces are easier than the whole.
Brute force is another pattern: try every possibility until one works. It is simple and always correct, but often too slow for large inputs.
The greedy method builds an answer step by step, always grabbing the option that looks best right now. Greedy choices are fast, but they only pay off when the problem has the right structure, so you must check that local picks lead to a global answer.
Reductions go the other direction. If you can rewrite your problem as a problem you already know how to solve, you inherit a ready-made solution.
Knowing these paradigms means meeting a new problem and asking: can I split it, can I search it, can I build it greedily, or can I map it to something solved?
2 · Watch
به انگلیسیTake it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.