Close
Register
Close Window

Data Structures and Algorithms Y

Chapter 1 Mathematical Background

Show Source |    | About   «  1.5. Summations   ::   Contents   ::   1.7. Mathematical Proof Techniques  »

1.6. Recurrence Relations

1.6.1. Recurrence Relations

The running time for a recursive algorithm is most easily expressed by a recursive expression because the total time for the recursive algorithm includes the time to run the recursive call(s). A recurrence relation defines a function by means of an expression that includes one or more (smaller) instances of itself. A classic example is the recursive definition for the factorial function:

\[\begin{split}n! = (n-1)! \cdot n\ \mbox{for}\ n>1; \quad 1! = 0! = 1.\end{split}\]

Another standard example of a recurrence is the Fibonacci sequence:

\[\begin{split}\mbox{Fib}(n) = \mbox{Fib}(n-1) + \mbox{Fib}(n-2)\ \mbox{for}\ n>2; \quad\mbox{Fib}(1) = \mbox{Fib}(2) = 1.\end{split}\]

From this definition, the first seven numbers of the Fibonacci sequence are

\[1, 1, 2, 3, 5, 8,\ \mbox{and}\ 13.\]

Notice that this definition contains two parts: the general definition for \(\mbox{Fib}(n)\) and the base cases for \(\mbox{Fib}(1)\) and \(\mbox{Fib}(2)\). Likewise, the definition for factorial contains a recursive part and base cases.

Recurrence relations are often used to model the cost of recursive functions. For example, the number of multiplications required by a recursive version of the factorial function for an input of size \(n\) will be zero when \(n = 0\) or \(n = 1\) (the base cases), and it will be one plus the cost of calling fact on a value of \(n-1\). This can be defined using the following recurrence:

\[\begin{split}\mathbf{T}(n) = \mathbf{T}(n-1) + 1\ \mbox{for}\ n>1; \quad \mathbf{T}(0) = \mathbf{T}(1) = 0.\end{split}\]

As with summations, we typically wish to replace the recurrence relation with a closed-form solution. One approach is to expand the recurrence by replacing any occurrences of \(\mathbf{T}\) on the right-hand side with its definition.

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

A slightly more complicated recurrence is

\[\mathbf{T}(n) = \mathbf{T}(n-1) + n; \quad \mathbf{T}(1) = 1.\]

Again, we will use expansion to help us find a closed form solution.

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

   «  1.5. Summations   ::   Contents   ::   1.7. Mathematical Proof Techniques  »

nsf
Close Window