Lesson 1 · Algorithmic Paradigms

Divide and Conquer

Divide and conquer is a paradigm that breaks a complex problem into identical, smaller subproblems, recursively solves them, and combines their solutions.

The three steps

Divide and conquer follows three phases: Divide the problem into smaller subproblems, Conquer the subproblems recursively, and Combine the results into a solution for the original problem.

This approach is powerful for problems that naturally split, such as sorting or searching.

Divide: Split the input
Conquer: Solve recursively
Combine: Merge sub-solutions

Base cases

Every recursive algorithm must have a base case to terminate. In divide and conquer, the base case is usually when the subproblem is small enough to be solved directly, such as an array of size 1.

Without a proper base case, the recursion will continue infinitely, leading to a stack overflow.

Identify the smallest subproblem
Return immediate answers for base cases
Prevents infinite recursion

Code example

Divide, conquer, and combine a maximum

def maximum(a, lo, hi):
    if lo == hi:
        return a[lo]
    mid = (lo + hi) // 2
    return max(maximum(a, lo, mid), maximum(a, mid + 1, hi))

a = [2, 9, 4, 7]
print("Maximum:", maximum(a, 0, len(a) - 1))

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <tuple>
#include <array>
#include <numeric>
using namespace std;
int maximum(vector<int>&a,int l,int r)
{
  if(l==r)return a[l];
  int m=(l+r)/2;
  return max(maximum(a,l,m),maximum(a,m+1,r));
}
int main()
{
  vector<int>a=
  {
    2,9,4,7
  };
  cout<<"Maximum: "<<maximum(a,0,3);
}

class Main
{
  static int maximum(int[]a,int l,int r)
  {
    if(l==r)return a[l];
    int m=(l+r)/2;
    return Math.max(maximum(a,l,m),maximum(a,m+1,r));
  }
  public static void main(String[]z)
  {
    int[]a=
    {
      2,9,4,7
    };
    System.out.print("Maximum: "+maximum(a,0,3));
  }
}

Input[2,9,4,7]

OutputMaximum: 9

Example

Run the example step by step

Output

Complexity analysis

The time complexity of a divide and conquer algorithm is often determined by the Master Theorem, which considers the number of subproblems, the size of each subproblem, and the cost of combining them.

For example, Merge Sort divides the array into two halves and takes O(N) to merge, resulting in O(N log N) time.

Use the Master Theorem
Logarithmic factors arise from halving
Combine step dictates the non-recursive overhead

Drawbacks

While elegant, recursion has overhead. Each recursive call consumes stack space, which can lead to memory exhaustion on deep recursions.

Additionally, if subproblems overlap, divide and conquer can redundantly compute the same results. In such cases, dynamic programming is a better fit.

Recursive call overhead
Requires O(log N) or more stack space
Inefficient for overlapping subproblems

Recurrences account for every level

The running time separates recursive work from local work: T(n)=aT(n/b)+f(n). Here a is the number of subproblems, n/b their size, and f(n) the cost of dividing and combining. Writing the recurrence forces the analysis to include work that informal 'halves each time' explanations often omit.

A recursion tree shows how cost spreads by level. Merge sort has log n levels each doing Θ(n) merge work, yielding Θ(n log n); binary search follows only one half and does constant local work, yielding Θ(log n).

Write a, b, and f(n)
Sum work across levels
Different combine costs change the answer

The Master Theorem has boundaries

The Master Theorem applies to sufficiently regular recurrences of the form aT(n/b)+f(n). It compares leaf-growth n^(log_b a) with non-recursive work. It does not automatically handle unequal subproblem sizes, data-dependent splits, or recurrences such as T(n)=T(n−1)+n.

Quicksort demonstrates why balance matters: good pivots create logarithmic depth and Θ(n log n) expected work, while consistently extreme pivots create a chain and Θ(n²) work. The paradigm does not guarantee speed by itself.

Check theorem preconditions
Balance controls recursion depth
Worst-case splits still matter

Implementation discipline and base cases

Every recursive call must receive a strictly smaller problem, and base cases must cover the smallest legal inputs. Define whether intervals are closed [l,r] or half-open [l,r); mixing conventions causes missing elements or infinite recursion. Compute mid as l+(r−l)/2 in fixed-width languages. If the combine step needs a temporary buffer, count it in auxiliary space and decide whether one buffer can be reused across levels.

Test empty input if supported, one item, two items, odd sizes, already ordered data, and adversarial inputs for the chosen split. Trace both the descent and the combine phase: showing only the recursion tree omits where many divide-and-conquer algorithms perform most of their work. Parallel execution is possible only when subproblems are independent, and speedup may be limited by the sequential combine step and scheduling overhead.

Finally, compare the recurrence prediction with measured recursion depth and operation counts on powers of two and nearby odd sizes. The experiment catches accidental overlap, repeated copying, and unbalanced partitions that the intended recurrence does not describe.

Shrink every recursive call
Keep one interval convention
Account for combine storage and work