On this concept: Formula

Not sure which lesson to do first? Find your level and get a plan →

CS Thinking · Computational Thinking · Grade 9-12

Divide and Conquer

Divide and conquer is an algorithmic strategy that splits a problem into smaller subproblems of the same kind, solves those smaller problems, and then combines their solutions into one final answer.

T(n)=aT(n/b)+f(n)

Quick Answer

Divide and conquer is an algorithmic strategy that splits a problem into smaller subproblems of the same kind, solves those smaller problems, and then combines their solutions into one final answer. It has three moves: divide the input (often in half), conquer each part the same way until the parts are trivial, and combine the partial answers. Use it when the answer for the whole can be built cheaply from answers for its parts: merge sort combines two sorted halves, and x16 can be found by squaring x8.

Why This Matters

Divide and conquer is behind many of the fastest known algorithms: merge sort's O(nlog⁡n), fast multiplication of huge numbers, and the Fast Fourier Transform used in audio and image processing. Its parts are independent, so the work splits naturally across many processors. The recurrence T(n)=aT(n/b)+f(n) predicts the cost before you write code, and it shows when a lopsided split or an expensive combine step wipes out the gain.

Intuitive Explanation

Suppose you need 316. Multiplying 3 by itself over and over takes 15 multiplications. But 316=(38)2, and 38=(34)2, and so on down to 31=3. Square four times: 32=9, 34=81, 38=6561, 316=43,046,721. That is 4 multiplications instead of 15. A problem of size 16 became one problem of size 8 plus a cheap combine step, a single squaring.

Every divide-and-conquer algorithm has the same three parts. Divide: split the input into a subproblems of size n/b. Conquer: solve each with the same method, stopping at a base case small enough to answer directly. Combine: build the full answer from the partial ones, at cost f(n). Together they give T(n)=aT(n/b)+f(n). Merge sort makes 2 calls on halves and merges in linear time, T(n)=2T(n/2)+n, which works out to O(nlog⁡n). The power example makes 1 call on half and does 1 multiplication, T(n)=T(n/2)+1, which is O(log⁡n).

Not every split is divide and conquer. Planning a party by splitting it into food, music and invitations is decomposition: the parts are different kinds of problem, so no single method repeats on them. Divide and conquer needs subproblems of the same kind as the original, solved by the same method, plus an explicit combine step. The split must also make real progress. Cutting off one item at a time, T(n)=T(n−1)+n, gives O(n2), no better than a simple approach.

Think of it like this. Counting a national vote works like divide and conquer: each town counts its own ballots, each region adds up its towns' totals, and the country adds up its regions. Every level does the same job, counting, on a smaller piece, and the totals combine on the way up. All the towns can count at once, the same reason these algorithms split well across processors.

Core idea. The same solving pattern repeats on smaller pieces until the pieces are easy enough to solve directly.


When to Use

Use divide and conquer when the input can be split into smaller pieces of the same kind, each piece can be solved by the same method, and the partial answers can be combined cheaply: sorting, searching sorted data, multiplying large numbers, finding the closest pair of points. Write the recurrence to check that the split pays off. If the parts are different kinds of task, that is Decomposition. If the smaller subproblems overlap and repeat, as in Fibonacci, store their answers (dynamic programming) instead of recomputing them.

Tip. Ask: Is the problem split into smaller problems of the same kind whose answers are then combined?

How to Recognize It

Check three things about the parts: whether they are the same kind of problem as the whole, whether all of them get solved, and whether their answers get joined.

  1. Is each part a smaller copy of the original problem, so the same method works on it?

    Yes is divide and conquer. If the parts are different kinds of jobs, like buying food and sending invitations, it is ordinary Decomposition.

  2. Are all the parts solved, not just one of them?

    Yes fits divide and conquer. If one half is thrown away after a single comparison, as in Binary Search, the method only shrinks the problem.

  3. Is there a step that builds the final answer out of the parts' answers?

    Yes is the combine step, such as merging two sorted halves. Without it, a function calling itself on a smaller input is plain Recursion, as in counting down from 10.

  4. Does splitting stop at pieces small enough to solve directly, such as a single item?

    Yes gives the base case every divide-and-conquer method needs. If the split never makes the pieces smaller, the method never finishes.

Divide and Conquer vs Decomposition vs Recursion vs Binary Search

Divide and conquer is a special kind of decomposition, is usually written with recursion, and looks a lot like binary search. Ask whether the parts are the same kind of problem, whether all are solved, and whether answers are combined.

Divide and Conquer

Meaning
Divide and conquer splits a problem into smaller problems of the same kind, solves each, and combines their answers.
Key test
Same-kind parts, all of them solved, then a combine step.
Formula
T(n)=aT(n/b)+f(n)
Example
Finding the closest pair among 1,000 points by solving the left and right halves, then checking pairs near the dividing line.

Decomposition

Meaning
Decomposition breaks a complex problem into smaller parts, which can be completely different kinds of task.
Key test
The parts can differ in kind, and each may need its own method.
Example
Making a video game split into art, music, level design and code.

Recursion

Meaning
Recursion is a function solving a problem by calling itself on a smaller input until it reaches a base case.
Key test
One self-call on a smaller input is enough; no splitting or combining is required.
Formula
sum(n)=n+sum(n−1)
Example
sum(4) = 4 + sum(3) = 4 + 3 + sum(2), and so on down to sum(0) = 0, giving 10.

Binary Search

Meaning
Binary search looks for a target in sorted data by checking the middle and continuing in only one half.
Key test
Only one half is ever worked on, and nothing is combined.
Formula
T(n)=T(n/2)+O(1)
Example
Looking for 64 among the sorted numbers 1 to 128 by comparing with the middle value each time.

Formula & Notation

T(n)=aT(n/b)+f(n)
A divide-and-conquer algorithm recursively solves subproblems and is often modeled by a recurrence of the form T(n)=aT(n/b)+f(n), where a subproblems of size n/b are combined with extra work f(n).

Worked Examples

Example 1 — Find the maximum by halves

Easy

Find the largest value in [7, 2, 9, 4, 1, 8, 6, 3] by divide and conquer. Count the comparisons and the rounds of combining, and compare with a single scan.
Show the steps and the answer
  1. Divide: split the list into halves, then quarters, down to the pairs [7, 2], [9, 4], [1, 8], [6, 3].

    Each piece is the same problem, 'find the largest', on fewer items.

  2. Conquer the pairs: 7, 9, 8 and 6, one comparison each, 4 in all.

    A pair is small enough to answer directly with one comparison, the base case.

  3. Combine upward: max(7, 9) = 9 and max(8, 6) = 8 with 2 comparisons, then max(9, 8) = 9 with 1.

    The largest value of the whole list must be the larger of the two halves' largest values, so each combine costs one comparison.

  4. Count: 4 + 2 + 1 = 7 comparisons, matching T(n)=2T(n/2)+1 with T(1)=0, which gives n−1.

    That equals a plain scan, but the four pair comparisons are independent, so four processors could finish in 3 rounds instead of 7 steps.

Answer: The maximum is 9, found with 7 comparisons in 3 rounds.

Takeaway: Divide, solve the tiny pieces directly, and combine with a cheap step. Here the gain is not fewer comparisons but independent work that can run in parallel.

Example 2 — Divide and conquer or decomposition?

Standard

Plan A for a school website: split the work into a login page, a news page and a photo gallery, and build each. Plan B for counting the words in a 400-page book: split it into two 200-page halves, count each half the same way, and add the counts. Which plan is divide and conquer? If Plan B keeps halving down to single pages, how many additions combine the results?
Show the steps and the answer
  1. Plan A: the three parts are different kinds of work, each needing its own design.

    No single method repeats on the parts, so this is decomposition, not divide and conquer.

  2. Plan B: each half is the same problem, counting the words in some pages, so the same method applies to halves, then quarters, down to single pages.

    Subproblems of the same kind, solved by the same method, are the mark of divide and conquer.

  3. Plan B's combine step: total = left count + right count, one addition per combine.

    An explicit combine step is the third part every divide-and-conquer method needs.

  4. Count the additions: each one joins two counts into one, so going from 400 page counts to 1 total takes 400 − 1 = 399 additions.

    Every addition reduces the number of separate counts by exactly one.

Answer: Plan B is divide and conquer, using 399 additions to combine 400 page counts. Plan A is decomposition, because its parts are different kinds of problem.

Takeaway: Divide and conquer splits into smaller copies of the same problem and combines them; splitting into different jobs is decomposition.

Example 3 — Find the mistake: splitting off one item

Application

Kim writes sort(list): remove the first item, sort the rest, then insert the removed item into its place, which takes up to n − 1 comparisons. She says: "It splits the problem, so it's divide and conquer and runs in O(nlog⁡n) like merge sort." Find the mistake and correct it.
Show the steps and the answer
  1. Write the recurrence: one subproblem of size n−1 plus up to n−1 comparisons to insert, so T(n)=T(n−1)+(n−1).

    A divide-and-conquer cost comes from how big the pieces are and how much the combine step costs.

  2. Unroll it: T(n)=(n−1)+(n−2)+⋯+1=n(n−1)/2.

    Each level removes only one item, so there are n levels instead of about log⁡2n.

  3. Put in n = 1,000: 1000⋅999/2=499,500 comparisons, against about 1000log⁡21000≈10,000 for merge sort.

    Both methods 'solve a smaller problem', yet their costs differ by a factor of about 50.

  4. Fix the split: cut the list into two halves of size n/2, sort both, and merge them, giving T(n)=2T(n/2)+n, which is O(nlog⁡n).

    Balanced halves make the problem size halve at every level, which is where the speed comes from.

Answer: Kim's method is O(n2), about 499,500 comparisons for 1,000 items. Splitting into two halves and merging, as merge sort does, gives O(nlog⁡n), about 10,000.

Takeaway: Peeling off one item at a time is barely dividing. The pieces must shrink by a constant factor, such as half, to get the log⁡n levels that make divide and conquer fast.

Where You'll See It

  • Finding a word in a dictionary by halving

    You open the dictionary in the middle, decide which half your word is in, then repeat on that half — each step throws away half the pages, which is the divide-and-conquer idea behind binary search.

  • Grading 200 quizzes with four helpers

    Split the stack into four piles, each person grades and totals their pile, then you add the four subtotals — solving smaller same-shaped subproblems and combining the results is divide and conquer.

  • A single-elimination tournament bracket

    The field splits into halves, each half plays down to one winner, and the two winners meet in the final — the bracket is literally divide (split), conquer (sub-tournaments), combine (championship game).

Common Mistakes

  1. The slip: Any algorithm that breaks a problem into parts is divide and conquer.

    Why it's tempting: The name just says 'divide,' so splitting anything seems to qualify.

    Instead: True divide and conquer splits into subproblems of the SAME KIND as the original (so the same method recurses), then COMBINES their solutions. Splitting into unrelated steps is just decomposition, not divide and conquer.

  2. The slip: Once the recursive calls return, the problem is solved — there is nothing left to do.

    Why it's tempting: The subproblems were the hard part, so it feels like the work is over when they finish.

    Instead: Most divide-and-conquer algorithms need a combine step (like merging sorted halves) after the recursion. Forgetting to combine leaves you with separate answers instead of one final answer.

  3. The slip: Splitting the input is enough; the recursion will stop on its own once the pieces get small.

    Why it's tempting: Each split seems to make the problem smaller, so it feels like the calls must finish eventually.

    Instead: Every divide-and-conquer method needs a base case answered directly, like a 1-item list in merge sort, and each split must make the input strictly smaller. Halving [5] with no base case gives [] and [5] again, so the same call repeats forever.


Mini Practice

Try these on your own. Tap Reveal when you want to check.

  1. Find the maximum of [7, 2, 9, 4, 1, 8, 6, 3] by divide and conquer: split in half until pieces have 2 items, then combine by keeping the larger value. Show each level.

    Hint: Start with the four pairs, then combine the winners two at a time.

  2. Compute 216 using xn=(xn/2)2. How many multiplications does this take, compared with multiplying by 2 one step at a time?

    Hint: Go from 21 to 22 to 24, squaring each time.

  3. A divide-and-conquer algorithm has T(n)=2T(n/2)+n with T(1)=1. Compute T(8).

    Hint: Build up: find T(2), then T(4), then T(8).

  4. Binary search checks the middle and then keeps searching only one half. Write its running time as T(n)=aT(n/b)+f(n). What are a, b and f(n)?

    Hint: How many halves are searched, how big is each, and how much work is done per step?

  5. Planning a school fair, you split the work into food, games and posters. Is this divide and conquer or decomposition?

    Hint: Are the parts smaller copies of the same problem?

  6. A student sorts [6, 1, 5, 2] by splitting it into [6, 1] and [5, 2], sorting each to get [1, 6] and [2, 5], then writing the answer as [1, 6, 2, 5]. Correct it.

    Hint: What step comes after the smaller problems are solved?

Want the full set?

50 practice questions for this concept — free to try, every one with a complete worked solution showing the why, not just the answer.

Frequently Asked Questions

When does dividing a problem actually save time?

When combining is cheap compared with solving the whole thing directly. Merge sort pays about nn steps per level to merge but ends at about nlog⁡2nn \log_2 n steps instead of the n2/2n^2/2 of a simple sort. If combining costs as much as the original problem, splitting buys nothing. The recurrence makes this precise: the number of parts aa, their size n/bn/b and the combine cost f(n)f(n) together set the total.

What is a classic example besides sorting?

Multiplying huge numbers. Multiplying two 1,000-digit numbers the school way needs about a million single-digit products. Karatsuba's method splits each number into two halves and gets the answer from three half-size multiplications instead of four, repeating the trick on each half. That brings the work down to roughly n1.58n^{1.58} digit products, under 60,000 for 1,000 digits, which is why computers use it for very large numbers.

Is divide and conquer always written with recursion?

Usually, because recursion matches the idea neatly: the function solves the smaller pieces by calling itself. But it does not have to be. Merge sort can be written bottom-up with loops: first merge pairs of single items, then pairs of 2-item runs, then 4-item runs, until one run covers the list. The work is the same; only the bookkeeping moves from the call stack into loops.

Learning Path

Divide and Conquer

You are here

You need Decomposition (splitting a problem into parts) and Recursion (a function calling itself on a smaller input, with a base case) first. Divide and Conquer adds the three-step pattern of divide, conquer and combine, and the recurrence T(n)=aT(n/b)+f(n) for its cost. Next, Merge Sort is the classic example in full, and Algorithm Efficiency turns recurrences into Big-O classes.

See Also