Divide and Conquer Examples: 47 Problems with Answers

Worked examples of Divide and Conquer to try before you open each solution, then practice problems with answers.

Worked Examples

Example 1

medium
Power by repeated squaring computes x32. How many multiplications, and how does it compare to naive?
Show solution

Answer

5 vs 31

First step

1.
x32=((((x2)2)2)2)2.

See the full worked solution + why-it-works coaching

SetupKey insightWhy it worksCommon pitfallConnection

Free: full solutions on 3 topics a day. No card.

Every topic, every day: the Family plan

Example 2

medium
Find max of [3,1,4,1,5,9,2,6] by divide and conquer. Show the combine.

Example 3

medium
Binary search on [1,3,5,7,9,11,13,15,17] for 13. Trace indices examined (0-indexed).

Example 4

medium
You compute x20 by repeated squaring. List the steps.

Example 5

hard
Strassen's matrix multiplication has T(n)=7T(n/2)+O(n2). Compute the complexity.

Example 6

hard
Closest pair of points in 2D has T(n)=2T(n/2)+O(n) with careful combine. Complexity?

Example 7

challenge
FFT has T(n)=2T(n/2)+O(n). State the complexity and one application.

Practice Problems

Try each one, then open the solution to compare your method.

Example 1

easy
Binary search halves a sorted list of 16 elements each step. How many comparisons (worst case) to narrow it to 1 element?

Example 2

easy
Merge sort splits a list of 8 items in half repeatedly until single items remain. How many levels of splitting occur?

Example 3

easy
A divide-and-conquer algorithm splits a problem into two halves and does O(n) work to combine. Write its recurrence T(n).

Example 4

easy
To find the maximum of 8 numbers by divide and conquer, you split into two halves, find each half's max, then combine. What is the combine step?

Example 5

easy
A list of 32 elements is repeatedly halved. After how many halvings is the size reduced to 1?

Example 6

easy
Which of these is a base case for a divide-and-conquer sort: (a) a list of 1 element, (b) a list of 1000 elements, (c) an unsorted list?

Example 7

easy
Binary search on 1000 sorted items takes at most about how many comparisons?

Example 8

easy
A divide-and-conquer algorithm splits into 3 subproblems of size n/3 with constant combine work. Write the recurrence.

Example 9

medium
Merge sort sorts n=8 items. Each of the log⁡28 levels does O(n) merge work. Estimate total comparisons in Big-O terms and as a count of level-work units.

Example 10

medium
Solve the recurrence T(n)=2T(n/2)+O(1) with T(1)=1 for n=8 by unrolling, and give the Big-O.

Example 11

medium
A flawed divide-and-conquer routine splits a list of size n into one piece of size n−1 and one of size 1. What is its depth and resulting complexity?

Example 12

medium
Using the recurrence T(n)=2T(n/2)+n, compute T(4) given T(1)=0.

Example 13

medium
Quicksort partitions around a pivot, then recurses on both sides. On an already-sorted list with the first element as pivot, why does it become O(n2)?

Example 14

medium
A divide-and-conquer power algorithm computes xn as (xn/2)2. How many multiplications to compute x16?

Example 15

medium
Three friends compute the sum of 1000 numbers by each summing a third, then adding the three subtotals. Is this divide and conquer, and what is the combine step?

Example 16

medium
Binary search looks for 7 in [1,3,5,7,9,11,13] (indices 0-6). Trace the indices examined.

Example 17

medium
A tournament of 64 players uses single elimination (halving each round). How many rounds until one winner?

Example 18

challenge
Karatsuba multiplies two n-digit numbers with recurrence T(n)=3T(n/2)+O(n). Using the Master Theorem, what is its complexity? (Naive is O(n2).)

Example 19

challenge
Prove by unrolling that T(n)=2T(n/2)+n with T(1)=0 gives T(n)=nlog⁡2n, and verify at n=8.

Example 20

challenge
You must find both the min and max of n numbers using as few comparisons as possible. A divide-and-conquer pairing approach uses about how many comparisons, versus the naive 2n−2?

Example 21

easy
Binary search halves a sorted list of 64 items. How many comparisons (worst case) to isolate one item?

Example 22

easy
A divide-and-conquer algorithm splits into 4 subproblems of size n/4 with O(n) combine. Write its recurrence T(n).

Example 23

easy
A list of 128 items is repeatedly halved. After how many halvings is the size 1?

Example 24

easy
Binary search on a sorted list of 1,000,000 items uses at most about how many comparisons?

Example 25

easy
For merge sort, what is the base case?

Example 26

easy
Binary search in [2,4,6,8,10,12,14,16] for 10. What is the first index examined?

Example 27

medium
Solve T(n)=2T(n/2)+n with T(1)=0 at n=16.

Example 28

medium
T(n)=2T(n/2)+n with T(1)=0. Compute T(8).

Example 29

medium
Quicksort on a random list has average-case complexity ___.

Example 30

medium
A tournament with 128 players uses single elimination. How many rounds?

Example 31

medium
Solve T(n)=4T(n/2)+n via master theorem.

Example 32

medium
A divide-and-conquer alg has T(n)=T(n/2)+O(1). Complexity?

Example 33

medium
For merge sort on n=32, total comparisons are about nlog⁡2n. Estimate.

Example 34

hard
Solve T(n)=2T(n/2)+nlog⁡n with master theorem.

Example 35

hard
Counting inversions in a list uses modified merge sort with T(n)=2T(n/2)+O(n). Complexity?

Example 36

hard
Why must a divide-and-conquer recursion have a base case strictly smaller than the original?

Example 37

hard
Quicksort with median-of-three pivot avoids the worst case on sorted inputs. What recurrence does it now satisfy on average?

Example 38

hard
Find the k-th smallest using Quickselect: T(n)=T(n/2)+O(n) on average. Complexity?

Example 39

challenge
Compute closed-form for T(n)=3T(n/2)+n via master theorem.

Example 40

challenge
You must find min AND max of n items together. Show that ≈3n2−2 comparisons suffice using pairwise divide-and-conquer.

What to focus on

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

Common stuck point: You still need a clear combine step. Splitting a problem is not enough if you cannot reconstruct the final answer.

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

Concept recap

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 is a structured form of decomposition often paired with recursion.

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.

Read the full lesson on Divide and Conquer

Common mistakes to watch for

Background knowledge

These ideas may be useful before you work through the harder examples.

decompositionrecursion