Recurrence Relations

• A recurrence is an equation that describes a function in terms of its value on smaller inputs.

• We can solve recurrences using the following approaches

  • Substitution - Guess the form of the solution and then use mathematical induction to find the constraints and show the solution works.

  • Repertoire Method ¹ - first find settings of general parameters for which the solution is known

    Then obtain the general case by combining the special cases.

    • This method is built upon the possibility of combining two recurrences, which usually comes from using linear combinations. In particular, let

      be a linear recurrence relation.

      We identify building blocks (functions) of that can be linearly combined

      The consider the generalized representation

      And solve the simpler recurrences

      The set of forms the repertoire.

      We then determine the constants and deduce the solution for

      The constant is determined using the initial condition

  • Recursion Tree Method. We draw out a recursion tree where each node represents the cost of a single subproblem. We then sum all the costs per level of the tree, and then across all levels to obtain the cost of the whole tree.

    We typically use this to make an ansatz that can be further refined.

• Master Method. This allows us to solve recurrences of the form

  Where and are constants and is an asymptotically positive function.

  We implicitly assume that the problem is divided into equal subproblems

  Let denote the critical exponent

  has the following asymptotic bounds ^{2 3}

  • If then

    If the time to divide is dominated by the time to conquer, then the splitting term does not appear.

  • If , where , then

    If the time to divide is equivalent to the time to conquer, then we have a splitting term

    • If , then
    • If , then
    • If , then

  • If and if for and sufficiently large (this additional constraint is the regularity condition), then .

    If the time to divide dominates the time to conquer, this doesn’t yield anything unless the regularity condition holds.

• The Akra-Bazzi method is a generalization of the master theorem that assumes subproblems are divided into equal sizes.

  We can apply the method to recurrences of the form

  • We assume the following:

    There are sufficient base cases provided and are constants such that and .

    where is a constant

    .

    is constant

  • The asymptotic behavior of is found by determining the value of for which

    And

Links §

• Cormen, Leiserson, Rivest, and Stein
• Knuth, Graham and Patashnik

Footnotes §

1. From Concrete Mathematics ↩

2. For a proof, see CLRS Ch. 4.6 ↩

3. Observe that denotes the number of subproblems and denotes the relative problem size. ↩