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:

Another standard example of a recurrence is the Fibonacci sequence:

$$\mbox{Fib}(n) = \mbox{Fib}(n-1) + \mbox{Fib}(n-2)\ \mbox{for}\ n>2; \quad\mbox{Fib}(1) = \mbox{Fib}(2) = 1.$$

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

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:

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.

1 / 8 Settings

<<<>>>

We will use expansion to guess the closed form solution for the recurrence $\mathbf{T}(n) = \mathbf{T}(n-1) + 1$ for $n > 1$; $\mathbf{T}(0) = \mathbf{T}(1) = 0$.

n

n-1

 1 + 

n-2

 1 + 

n-3

 1 + 

n-4

 1 + 

1

$\displaystyle\sum_{i=1}^{n}1$

Saving...
Server Error
Resubmit

A slightly more complicated recurrence is

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

1 / 8 Settings

<<<>>>

We will use expansion to guess the closed form solution for the recurrence $\mathbf{T}(n) = \mathbf{T}(n-1) + n\ \mbox{for}\ n > 1; \mathbf{T}(1) = 1$.

n

n-1

 n + 

n-2

 n-1 + 

n-3

 n-2 + 

n-4

 n-3+ 

1

$\displaystyle\sum_{i=1}^{n}i$

Saving...
Server Error
Resubmit