Divide and Conquer Strategies

Divide and conquer is one of the most powerful algorithm design paradigms in Computer Science. It solves a problem by breaking it into smaller sub-problems of the same type, solving each sub-problem recursively, and then combining the results. At A-Level, you must understand the paradigm, be able to identify algorithms that use it, and analyse their complexity.

---

The Three Steps

Every divide and conquer algorithm follows three steps:

Step	Description	Example (Merge Sort)
Divide	Split the problem into smaller sub-problems	Split the array into two halves
Conquer	Solve each sub-problem recursively	Recursively sort each half
Combine	Merge the results of the sub-problems	Merge the two sorted halves

The recursion terminates at a base case — a sub-problem small enough to solve directly (e.g., an array of size 0 or 1 is already sorted).

---

Algorithms That Use Divide and Conquer

Algorithm	Divide	Conquer	Combine	Complexity
Binary search	Discard half the array	Search the relevant half	Return the result	O(log n)
Merge sort	Split into two halves	Recursively sort each half	Merge sorted halves	O(n log n)
Quick sort	Partition around pivot	Recursively sort partitions	No combine needed (in-place)	O(n log n) avg

---

Why Divide and Conquer Is Efficient

The key insight is that dividing a problem of size n into sub-problems of size n/2 (and doing O(n) work to combine) gives O(n log n) overall.

Recursion Tree for Merge Sort

Level 0:  [n elements]                    → O(n) merge work
Level 1:  [n/2]        [n/2]              → O(n) merge work
Level 2:  [n/4]  [n/4] [n/4]  [n/4]      → O(n) merge work
...
Level log₂(n): [1] [1] [1] ... [1]        → O(n) merge work

There are log₂(n) levels, and each level does O(n) work. Total: O(n log n).

---

Worked Example: Power Computation

Problem: Calculate xⁿ (x raised to the power n).

Naive Approach — O(n)

FUNCTION power(x, n)
    result = 1
    FOR i = 1 TO n
        result = result * x
    END FOR
    RETURN result
END FUNCTION

This performs n multiplications.

Divide and Conquer Approach — O(log n)

FUNCTION fastPower(x, n)
    IF n = 0 THEN
        RETURN 1
    END IF
    IF n is even THEN
        half = fastPower(x, n / 2)
        RETURN half * half
    ELSE
        RETURN x * fastPower(x, n - 1)
    END IF
END FUNCTION