Recurrence

Definition A recurrence is an equation that describes a

function in terms of its value on other, typically smaller, arguments.

• Note the difference from recursion.
• Recurrence relation: A function whose definition depends on itself.
• Algorithmic recurrence, and its threshold $n_0$, so that
  • $T(n)=\Theta (1)$ for $n<n_0$, and
  • Every path of recursion terminates in a defined base case within a finite number of recursive invocations for $n\ge n_0$.
• Approximations
  • The complexity does not depend on the threshold as long as it’s large enough to cover all base cases.
  • Ignoring floors and ceilings

Examples

• Architectures: hypercube, mesh, complete binary trees.
• binary-multiplication
• fibonacci

Solution

Solving the recurrence relationship to get closed-form solution. (Or just an asymptotic bound)

When can the floors and ceilings be ignored? Refer to Akra-Bazzi recurrence.

Substitution

• Guess the right form first, plug the bound back in to inductively prove it
• Subtracting a lower-order term from the guess may help, e.g. $T(n)\le cn-d$.
• Avoid using asymptotic-notation in the substitution proof, keep the basic definition, as the constant behind the anonymous notation is unclear. Prove the exact inductive hypothesis!
• For the guesses made
  • If $c$ doesn’t exist, the guess it too low
  • If $c\to 0$ as $n\to \infty$, the guess is too high

Recursion-Tree

• or iterative method
• Plug the equation back to itself, all the way down to base case, and derive the solution
• see Iterative Solution
• Unsure of the leaves? Write another recurrence $L(n)$ to characterize the number of leaves!

Master Method

Based on the master-theorem.

Akra-Bazzi method

See akra-bazzi.

Generating Function

See fibonacci.