Recursion

Recursive

A recursive algorithm or function is the one that calls itself to solve a smaller version of its task. Terminating or base conditions are required.

Divide & Conquer

• Divide
  Split a problem into smaller sub-problems.
• Conquer
  Solve a subset of smaller sub-problems recursively.
• Combine
  Combine the solutions to solve the initial problem.

Examples:

• Binary search
• Merge sort
• Quick sort
• Depth-first traversals

Analysis

Recurrence Relation

A mathematical equation that defines the overall cost of solving a problem in terms of the cost of solving its smaller sub-problems. It provides a way to express the time complexity of recursive algorithms.

3 common methods are used to solve a recurrence relation.

Substitution Method

The form of the solution is guessed and verified by induction. Then the constants are solved for.

Iteration Method

Aka. recursion-tree method. The recurrence is expanded step-by-step to identify patterns and dervice a solution. Good for generating guesses for substituion method but can be unreliable.

Master Theorem

For Decreasing Functions

Applies to below form:

Where $a, b \gt 0$ and $k \ge 0$.

Here are the cases:

• If $a \lt 1$ then $T(n) = O(n^k)$
• If $a=1$ then $T(n) = O(n^{k+1})$
• If $a \gt 1$ then $T(n) = O(n^{k} a^{n/b})$

For Dividing Functions

Applies to recurrences of the below form:

Where $a \ge 1$, $b \gt 1$ and $k \ge 0$.

Here are the cases:

• If $k < \log_b{a}$ then $T(n) = O(n^{\log_b a})$.
• If $k = \log_b{a}$ and $p<-1$ then $T(n) = O(n^k)$.
• If $k = \log_b{a}$ and $p=-1$ then $T(n) = O(n^k \log \log n)$.
• If $k = \log_b{a}$ and $p>-1$ then $T(n) = O(n^k \log^{p+1} n)$.
• If $k > \log_b{a}$ and $p\ge 0$ then $T(n) = O(n^k \log^p n)$.
• If $k > \log_b{a}$ and $p\lt 0$ then $T(n) = O(n^k)$.