# 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:
- Compute (or bound) the
*depth of the leaves* - Compute (or bound) the
*sum for each level* - Compute (or bound) the
*sum across all levels*

- Compute (or bound) the

### 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)\)