# Divide-and-Conquer

• Divide the problem into a number of subproblems that are smaller instances of the same problem
• Conquer (recursive case) the subproblems by solving them recursively. If the problem size is small enough, just solve them normally (base case)
• Combine the solutions to the subproblems into the solution of the original problem

## Recurrences

• Go hand in hand with divide-and-conquer paradigm
• Are a natural way to characterize the running times of divide-and-conquer algorithms
• Recurrence = equation or inequality that describes a function in terms of its value on smaller inputs

$$T(n) = \begin{cases} \Theta(1), & n = 1 \\ 2T(\frac{n}{2}) + \Theta(n), & n > 1 \end{cases}$$

• Subproblems are not necessarily constrained to being a constant fraction of the input size

$$T(n) = T(n - 1) + \Theta(1)$$

• There are 3 ways for obtaining asymptotic “$$\Theta$$” or “$$\mathcal{O}$$” bounds for recurrences
• Substitution method: guess a bound and then through mathematical induction prove it correct
• Recursion tree method: convert recurrence into a tree, where the nodes are the costs of the different levels of the recursion. Use bounding techniques to solve the recurrence
• Master theorem: “black box” for solving recurrences; provides bounds for recurrences of the form

$$T(n) = aT(\frac{n}{b}) + f(n) \quad, a \geq 1, b > 1$$

• $$a$$ = the number of subproblems we divide the problem into; or the branching factor in the recursion tree
• $$b$$ = division ratio; so the size of the subproblems
• $$f(n) = D(n) + C(n)$$, where $$D(n)$$ is the time it takes for the divide step and $$C(n)$$ is the time it takes for the combine step

## Recursion trees

• Nodes: labeled with the contribution to the total for that recursive call (not counting what happens inside the children)
• Children: one for each appearance of the recurrent term
• After drawing such a tree, we can solve the recurrence:
1. Compute (or bound) the depth of the leaves
2. Compute (or bound) the sum for each level
3. Compute (or bound) the sum across all levels

### Merge-sort recursion tree

• Depth of the leaves = $$\log n$$
• Sum for each level = $$cn$$
• Sum across all levels = $$cn \log n = \Theta(n \log n)$$

### Another example

• Let $$T(n) = T(\frac{n}{3}) + T(\frac{2n}{3}) + \mathcal{O}(n)$$

• Depth of the (deepest) leaves: $$\log_{3/2} n$$
• Sum for each level = $$\leq cn$$
• Sum across all levels = $$cn \log_{3/2} n = \mathcal{O}(n \log n)$$

## Master Theorem

• “Simple version”:

$$T(n) = aT(\frac{n}{b}) + \Theta(n^d)$$

• If $$a > b^d$$, then $$T(n) = \Theta(n^{\log_b a})$$
• If $$a = b^d$$, then $$T(n) = \Theta(n^d \log n)$$
• If $$a < b^d$$, then $$T(n) = \Theta(n^d)$$