Divide-and-conquer is a method for designing efficient algorithms. It works by recursively splitting a problem into smaller instances, solving them, and then combining their results. When a subproblem becomes small enough (the base case), it’s solved directly.

The three steps are:

1. Divide – break the problem into smaller subproblems.
2. Conquer – solve each subproblem recursively.
3. Combine – merge the subproblem solutions into the final result.

Recurrence

A recurrence is an equation (or inequality) that defines a function in terms of itself. It has:

• Recursive case – the function calls itself on smaller inputs.
• Base case – it stops recursing and gives a direct value.

If at least one function satisfies it, it’s well-defined; otherwise, ill-defined.

Algorithmic recurrences

A recurrence is algorithmic if, for every sufficiently large threshold , the following two properties hold:

1. For $(n < n_0):T(n) = Θ(1)$

   The running time for small inputs is constant (solved directly without recursion).

2. For $(n ≥ n_0)$ Every path of recursion terminates in a base case after a finite number of recursive calls.

For small inputs $(n < n_0)$, the algorithm must always return a result in finite time.

If the recursion does not terminate for $(n ≥ n_0)$, the algorithm is incorrect, as it would run infinitely.

Conventions for Recurrences

• If a recurrence is given without an explicit base case, we assume it is algorithmic.
• For most divide-and-conquer recurrences, dropping floors or ceilings does not change the asymptotic solution.
• Some recurrences are stated as inequalities:
  • $T(n) \le 2T(n/2) + Θ(n)$ → only an upper bound, so solution uses O-notation.
  • $T(n) \ge 2T(n/2) + Θ(n)$ → only a lower bound, so solution uses Ω-notation.