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?Repeated squaring for x^32: 5 squarings replace 31 naive multiplications
Show solution
Answer
5 vs 31
First step
1.
x32=((((x2)2)2)2)2.
See the full worked solution + why-it-works coaching
Setup·Key insight·Why it works·Common pitfall·Connection
Find max of [3,1,4,1,5,9,2,6] by divide and conquer. Show the combine.D&C max-finding tree for [3,1,4,1,5,9,2,6]: combine max(4, 9) = 9 at the root
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?Binary search halving tree for n = 16: 4 levels to reach size 1
Example 2
easy
Merge sort splits a list of 8 items in half repeatedly until single items remain. How many levels of splitting occur?Merge sort split tree for n = 8: 3 levels of splitting until all sublists have size 1
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?Halving chain for n = 32: count the 5 edges to reach size 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.Divide-and-conquer tree: one problem of size n splits into three subproblems of size n/3
Example 9
medium
Merge sort sorts n=8 items. Each of the log28 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.Recursion tree for T(n) = 2T(n/2) + O(1), n = 8: 8 leaf base cases dominate, giving O(n)
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.Recursion tree for T(n) = 2T(n/2) + n, n = 4: two levels deep, T(1)
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?Repeated-squaring chain for x^16: four squarings from x to x^16
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?Tournament halving tree for 64 players: count 6 rounds until one winner remains
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)=nlog2n, 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?Binary search on 64 items: 6 halvings trace the worst-case comparison path
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?Halving chain for n = 128: 7 edges from 128 down to the base case of 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).Recursion tree for T(n) = 2T(n/2) + n at n = 8: 3 levels × 8 work per level
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?Single-elimination tournament for 128 players: 7 rounds halve the field to 1 winner
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 nlog2n. Estimate.
Example 34
hard
Solve T(n)=2T(n/2)+nlogn 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 ≈23n−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.