Skip to main content

9. Recurrence Relations

03/03/23

Recurrence Relations​

  • Is a recursively-defined function. Applied to the case when the function is some measure of resources, might only want the big-Oh family properties of the solution
  • Suppose that the runtime of a program is T(n), then a recurrence relation will express T(n) in terms of its values at other (smaller) values of n

Simple Sorting​

  • Bubble sort do not naturally generate recurrence relations as they are not naturally recursive
  • But could be phrased that way, bubble sort, T(n)=T(n−1)+dnT(n)=T(n-1)+d n
    • dndn for a pass on the outer loop
    • T(n−1)T(n-1) for the remaining passes

Solving Recurrence​

General Pattern

  1. Starting from the base case, use the recurrence to work out many cases, by directly substituting and working upwards in values of n
  2. Inspect the results, look for a pattern and make a hypothesis for the general results
  3. Attempt to prove the hypothesis - typically using some form of induction Often then extract the large nn behaviour using big-Oh family. Can be long, tedious and error prone, but many cases are covered by a general rule with the name of "Master Theorem"