# Divide and Conquer Algorithm

**Divide** – break the problem into several subproblems that are similar to the original problem but smaller in size

**Conquer** – solve the subproblems recursively.

Base case: If the subproblem size is small enough (i.e., the base case has been reached) then solve the subproblem directly without more recursion.

**Combine** – the solutions to create a solution for the original problem

**Analysis of recursive algorithms**

Iterative algorithms can often be analyzed by counting instruction executions for some problem size

n, as was done for the Insertion sort.Recursive algorithms solve a problem based on recurring solution(s) to progressively smaller subproblem(s). Accurate analysis requires an accounting of this recurrence.

recurrence equation– describes the running time of a problem of sizenof an algorithm that contains a recursive call to itself, in terms of the running time on smaller inputs of the same problem type.T(n) = recurrence equation defining the running time on problem of size

n