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.
Showing a random 20 of 50 problems.
Example 1
medium
For merge sort on n=32, total comparisons are about nlog2n. Estimate.
Example 2
medium
Binary search on [1,3,5,7,9,11,13,15,17] for 13. Trace indices examined (0-indexed).
Example 3
medium
You compute x20 by repeated squaring. List the steps.
Example 4
challenge
FFT has T(n)=2T(n/2)+O(n). State the complexity and one application.
Example 5
medium
Binary search looks for 7 in [1,3,5,7,9,11,13] (indices 0-6). Trace the indices examined.
Example 6
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 7
hard
Solve T(n)=2T(n/2)+nlogn with master theorem.
Example 8
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 9
hard
Quicksort with median-of-three pivot avoids the worst case on sorted inputs. What recurrence does it now satisfy on average?
Example 10
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 11
challenge
Compute closed-form for T(n)=3T(n/2)+n via master theorem.
Example 12
challenge
You must find min AND max of n items together. Show that ≈23n−2 comparisons suffice using pairwise divide-and-conquer.
Example 13
easy
A divide-and-conquer algorithm splits into 4 subproblems of size n/4 with O(n) combine. Write its recurrence T(n).
Example 14
medium
Solve T(n)=4T(n/2)+n via master theorem.
Example 15
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 16
hard
Counting inversions in a list uses modified merge sort with T(n)=2T(n/2)+O(n). Complexity?
Example 17
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 18
hard
Strassen's matrix multiplication has T(n)=7T(n/2)+O(n2). Compute the complexity.
Example 19
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 20
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