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 size n of 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