Divide & Conquer

Divide and conquer breaks a problem into independent subproblems of the same type, solves each recursively, then combines the results. The key word is independent — the subproblems do not share state, which separates this technique from dynamic programming (which handles overlapping subproblems).

Three steps every divide-and-conquer algorithm follows:

Divide — split the input into smaller subproblems
Conquer — solve each subproblem recursively (base case stops recursion)
Combine — merge the subproblem solutions into the final answer

The Master Theorem

The Master Theorem gives a shortcut for solving recurrences of the form:

T(n) = a · T(n/b) + f(n)

Where:

a = number of subproblems at each level
b = factor by which input size shrinks
f(n) = cost of dividing and combining (work done outside the recursive calls)

Three cases (let p = log_b(a), the "critical exponent"):

| Case | Condition | Result | |------|-----------|--------| | Case 1 | f(n) = O(n^(p-ε)) for some ε > 0 | T(n) = Θ(n^p) — recursion dominates | | Case 2 | f(n) = Θ(n^p) | T(n) = Θ(n^p · log n) — tie | | Case 3 | f(n) = Ω(n^(p+ε)) and regularity condition | T(n) = Θ(f(n)) — combining dominates |

Note

Merge Sort: T(n) = 2T(n/2) + O(n). Here a=2, b=2, so p = log₂2 = 1. f(n) = O(n) = O(n¹) — Case 2. Result: T(n) = Θ(n log n). Correct!

Merge Sort

Merge sort is the canonical divide-and-conquer algorithm. Divide: split array in half. Conquer: sort each half. Combine: merge two sorted halves.

The merge step is where the real work happens — it produces a sorted sequence from two sorted subsequences in O(n) time.

// Merge Sort — O(n log n) time, O(n) space
function mergeSort(arr) {
  if (arr.length <= 1) return arr;  // base case

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));   // conquer left half
  const right = mergeSort(arr.slice(mid));      // conquer right half

  return merge(left, right);  // combine
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

  // Append any remaining elements
  return result.concat(left.slice(i)).concat(right.slice(j));
}

console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));
// [3, 9, 10, 27, 38, 43, 82]

// Count inversions using merge sort — O(n log n)
// An inversion is a pair (i,j) where i < j but arr[i] > arr[j]
function countInversions(arr) {
  if (arr.length <= 1) return { sorted: arr, count: 0 };

  const mid = Math.floor(arr.length / 2);
  const leftResult = countInversions(arr.slice(0, mid));
  const rightResult = countInversions(arr.slice(mid));

  let count = leftResult.count + rightResult.count;
  const merged = [];
  let i = 0, j = 0;
  const L = leftResult.sorted, R = rightResult.sorted;

  while (i < L.length && j < R.length) {
    if (L[i] <= R[j]) {
      merged.push(L[i++]);
    } else {
      // L[i] > R[j]: L[i..end] all invert with R[j]
      count += L.length - i;
      merged.push(R[j++]);
    }
  }

  return {
    sorted: merged.concat(L.slice(i)).concat(R.slice(j)),
    count
  };
}

console.log(countInversions([2, 4, 1, 3, 5]).count); // 3

Binary Search

Binary search is divide and conquer on a sorted array. Divide: compare the middle element with target. Conquer: recurse on the relevant half. Combine: trivial — the answer from the recursive call is the answer.

Recurrence: T(n) = T(n/2) + O(1). Master Theorem: a=1, b=2, p = log₂1 = 0. f(n) = O(1) = O(n⁰) — Case 2. T(n) = Θ(log n).

// Binary Search — O(log n)
function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;

  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);  // avoid integer overflow

    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }

  return -1;
}

console.log(binarySearch([1, 3, 5, 7, 9, 11], 7));  // 3
console.log(binarySearch([1, 3, 5, 7, 9, 11], 6));  // -1

Closest Pair of Points

Given n points in a 2D plane, find the pair with the minimum distance. Brute force is O(n²). Divide and conquer achieves O(n log n).

Algorithm:

Sort points by x-coordinate
Split at median x into left and right halves
Recursively find the minimum distance d_L and d_R in each half
Let d = min(d_L, d_R)
Check the "strip" — points within distance d of the dividing line
The strip has at most 8 relevant points per point (geometric argument), making step 5 O(n)

// Closest Pair of Points — O(n log² n) [O(n log n) with sorted strip]
function dist(p1, p2) {
  return Math.sqrt((p1.x - p2.x) ** 2 + (p1.y - p2.y) ** 2);
}

function closestPairBrute(points) {
  let minDist = Infinity;
  for (let i = 0; i < points.length; i++) {
    for (let j = i + 1; j < points.length; j++) {
      minDist = Math.min(minDist, dist(points[i], points[j]));
    }
  }
  return minDist;
}

function closestPair(points) {
  points.sort((a, b) => a.x - b.x);
  return closestPairHelper(points);
}

function closestPairHelper(points) {
  if (points.length <= 3) return closestPairBrute(points);

  const mid = Math.floor(points.length / 2);
  const midX = points[mid].x;

  const dLeft  = closestPairHelper(points.slice(0, mid));
  const dRight = closestPairHelper(points.slice(mid));
  let d = Math.min(dLeft, dRight);

  // Check strip of width 2d around the dividing line
  const strip = points.filter(p => Math.abs(p.x - midX) < d);
  strip.sort((a, b) => a.y - b.y);  // sort strip by y

  for (let i = 0; i < strip.length; i++) {
    for (let j = i + 1; j < strip.length && strip[j].y - strip[i].y < d; j++) {
      d = Math.min(d, dist(strip[i], strip[j]));
    }
  }

  return d;
}

const points = [
  { x: 2, y: 3 }, { x: 12, y: 30 }, { x: 40, y: 50 },
  { x: 5, y: 1 }, { x: 12, y: 10 }, { x: 3, y: 4 }
];
console.log(closestPair(points).toFixed(4)); // ~1.4142 (between (2,3) and (3,4))

Majority Element — Boyer-Moore Voting

Find the element that appears more than n/2 times (guaranteed to exist).

Divide and Conquer approach: The majority element of the whole array must be the majority element of at least one half. Recursively find the majority of each half, then verify which (if either) is the majority of the full array.

T(n) = 2T(n/2) + O(n). Master theorem gives O(n log n).

// Majority Element — Divide and Conquer O(n log n)
function majorityElementDC(nums) {
  function countInRange(num, lo, hi) {
    let count = 0;
    for (let i = lo; i <= hi; i++) {
      if (nums[i] === num) count++;
    }
    return count;
  }

  function helper(lo, hi) {
    if (lo === hi) return nums[lo];

    const mid = lo + Math.floor((hi - lo) / 2);
    const leftMajority  = helper(lo, mid);
    const rightMajority = helper(mid + 1, hi);

    if (leftMajority === rightMajority) return leftMajority;

    const leftCount  = countInRange(leftMajority, lo, hi);
    const rightCount = countInRange(rightMajority, lo, hi);
    return leftCount > rightCount ? leftMajority : rightMajority;
  }

  return helper(0, nums.length - 1);
}

// Boyer-Moore Voting — O(n) time, O(1) space (the optimal approach)
function majorityElementBM(nums) {
  let candidate = null;
  let count = 0;

  for (const num of nums) {
    if (count === 0) candidate = num;
    count += num === candidate ? 1 : -1;
  }

  return candidate;  // guaranteed to be correct since majority exists
}

console.log(majorityElementDC([2, 2, 1, 1, 1, 2, 2])); // 2
console.log(majorityElementBM([2, 2, 1, 1, 1, 2, 2])); // 2

Tip

Boyer-Moore is not divide-and-conquer but is the optimal solution. Knowing both demonstrates depth. The D&C version is useful for understanding why majority in one half implies majority in the whole.

Karatsuba Multiplication

Classic long multiplication of two n-digit numbers takes O(n²) operations. Karatsuba reduces this using a clever algebraic identity.

To multiply A × B where A = a1·10^(n/2) + a0 and B = b1·10^(n/2) + b0:

Instead of 4 multiplications (a1·b1, a1·b0, a0·b1, a0·b0), Karatsuba uses 3:

z2 = a1 · b1
z0 = a0 · b0
z1 = (a1 + a0)(b1 + b0) - z2 - z0 ← clever: this gives a1·b0 + a0·b1

Recurrence: T(n) = 3T(n/2) + O(n). Master Theorem: a=3, b=2, p = log₂3 ≈ 1.585. f(n) = O(n) = O(n¹) — Case 1 (p > 1). T(n) = Θ(n^log₂3) ≈ Θ(n^1.585) — faster than O(n²)!

// Karatsuba multiplication (BigInt version for accuracy)
function karatsuba(x, y) {
  // Base case
  if (x < 10n || y < 10n) return x * y;

  // Find the number of digits in the larger number
  const n = BigInt(Math.max(x.toString().length, y.toString().length));
  const half = n / 2n;
  const m = 10n ** half;

  const a1 = x / m;   // high half of x
  const a0 = x % m;   // low half of x
  const b1 = y / m;   // high half of y
  const b0 = y % m;   // low half of y

  const z2 = karatsuba(a1, b1);                    // 1st recursive call
  const z0 = karatsuba(a0, b0);                    // 2nd recursive call
  const z1 = karatsuba(a1 + a0, b1 + b0) - z2 - z0;  // 3rd recursive call

  return z2 * (m * m) + z1 * m + z0;
}

console.log(karatsuba(1234n, 5678n)); // 7006652n
console.log(1234n * 5678n);           // 7006652n — verify

Divide and Conquer vs Dynamic Programming

Property	Divide & Conquer	Dynamic Programming
Subproblems	Independent — no shared state	Overlapping — same subproblem solved repeatedly
Memoization needed	No	Yes (or tabulation)
Direction	Top-down only	Top-down (memo) or bottom-up (table)
Example	Merge sort, binary search	Fibonacci, coin change
Combining step	Non-trivial (merge)	Trivial (lookup table)

Complexity of Common D&C Algorithms

Algorithm	Recurrence	Result
Merge Sort	T(n) = 2T(n/2) + O(n)	O(n log n)
Binary Search	T(n) = T(n/2) + O(1)	O(log n)
Quicksort (avg)	T(n) = 2T(n/2) + O(n)	O(n log n)
Closest Pair	T(n) = 2T(n/2) + O(n log n)	O(n log² n)
Karatsuba	T(n) = 3T(n/2) + O(n)	O(n^1.585)
Strassen Matrix	T(n) = 7T(n/2) + O(n²)	O(n^2.807)

Key Takeaways

Divide at the midpoint (or by a factor b) to guarantee balanced subproblems
The combine step determines the total complexity — O(n) combine gives O(n log n) overall
Use the Master Theorem to quickly classify the time complexity
Independence of subproblems is the defining feature — if they overlap, use DP
D&C is parallelizable — subproblems can be solved on different processors
Recursion depth is O(log n), so stack space is O(log n) unless combine step allocates more