Start with the recap, study the fully worked examples, then use the practice problems to
check your understanding of Divide and Conquer.
This page combines explanation, solved examples, and follow-up practice so you can move
from recognition to confident problem-solving in CS Thinking.
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.
Break a big hard task into smaller versions of the same task, solve each one, then stitch the answers together.
Read the first worked example with the solution open so the structure is clear.
Try the practice problems before revealing each solution.
Use the related concepts and background knowledge badges if you feel stuck.
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.
Sense of Study hint:First define the base case. Then decide how the problem splits into smaller copies of itself. Finally, describe exactly how the smaller answers will be combined.
Common Mistakes to Watch For
Before you work through the examples, skim the mistake guide so you know which shortcuts and
sign errors to avoid.
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
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 these problems on your own first, 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) = 0 base cases
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 = T(8) = 24
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.