4 edited tags
| link
3 edited tags
| link
    Tweeted twitter.com/#!/StackCompSci/status/225358716919230464
2 this is specifically about sequences of numbers
source | link

How to solve Solving or approximating recurrence relations? for sequences of numbers

In computer science, we have often have to solve recurrence relationsrecurrence relations, that is find a closed formclosed form for a recursively defined sequence of numbers. When considering runtimes, we are often interested mainly in the sequence's asymptotic growthasymptotic growth.

Examples are

  1. theThe runtime of a tail-recursive function stepping downwards to $0$ from $n$ whose body takes time $f(n)$:

    $\qquad \begin{align} T(0) &= 0 \\ T(n+1) &= T(n) + f(n) \end{align}$

  2. theThe Fibonacci sequenceFibonacci sequence:

    $\qquad \begin{align} F_0 &= 0 \\ F_1 &= 1 \\ F_{n+2} &= F_n + F_{n+1} \end{align}$

  3. theThe number of Dyck wordsDyck words with $n$ parenthesis pairs:

    $\qquad\begin{align} C_0 &= 1 \\ C_{n+1}&=\sum_{i=0}^{n}C_i\,C_{n-i} \end{align}$

    and

  4. the MergesortThe mergesort runtime recurrence on lists of length $n$:

    $\qquad \begin{align} T(1) &= T(0) = 0 \\ T(n) &= T(\lfloor n/2\rfloor) + T(\lceil n/2\rceil) + n-1 \end{align}$

$\qquad \begin{align} T(1) &= T(0) = 0 \\ T(n) &= T(\lfloor n/2\rfloor) + T(\lceil n/2\rceil) + n-1 \end{align}$

What are methods to solve recurrence relations? We are looking for

  • general methods and
  • methods for a relevantsignificant subclass

as well as

  • methods that yield precise solutions and
  • suchmethods that provide (bounds on) asymptotic growth.

This is supposed to become a reference question. Please post one answer per method and provide a general description as well as an illustrative example.

How to solve recurrence relations?

In computer science, we have often have to solve recurrence relations, that is find a closed form for a recursively defined sequence of numbers. When considering runtimes, we are often interested mainly in the sequence's asymptotic growth.

Examples are

  1. the runtime of a tail-recursive function stepping downwards to $0$ from $n$ whose body takes time $f(n)$

    $\qquad \begin{align} T(0) &= 0 \\ T(n+1) &= T(n) + f(n) \end{align}$

  2. the Fibonacci sequence

    $\qquad \begin{align} F_0 &= 0 \\ F_1 &= 1 \\ F_{n+2} &= F_n + F_{n+1} \end{align}$

  3. the number of Dyck words with $n$ parenthesis pairs

    $\qquad\begin{align} C_0 &= 1 \\ C_{n+1}&=\sum_{i=0}^{n}C_i\,C_{n-i} \end{align}$

    and

  4. the Mergesort runtime recurrence on lists of length $n$

$\qquad \begin{align} T(1) &= T(0) = 0 \\ T(n) &= T(\lfloor n/2\rfloor) + T(\lceil n/2\rceil) + n-1 \end{align}$

What are methods to solve recurrence relations? We are looking for

  • general methods and
  • methods for a relevant subclass

as well as

  • methods that yield precise solutions and
  • such that provide (bounds on) asymptotic growth.

This is supposed to become a reference question. Please post one answer per method and provide a general description as well as an illustrative example.

Solving or approximating recurrence relations for sequences of numbers

In computer science, we have often have to solve recurrence relations, that is find a closed form for a recursively defined sequence of numbers. When considering runtimes, we are often interested mainly in the sequence's asymptotic growth.

Examples are

  1. The runtime of a tail-recursive function stepping downwards to $0$ from $n$ whose body takes time $f(n)$:

    $\qquad \begin{align} T(0) &= 0 \\ T(n+1) &= T(n) + f(n) \end{align}$

  2. The Fibonacci sequence:

    $\qquad \begin{align} F_0 &= 0 \\ F_1 &= 1 \\ F_{n+2} &= F_n + F_{n+1} \end{align}$

  3. The number of Dyck words with $n$ parenthesis pairs:

    $\qquad\begin{align} C_0 &= 1 \\ C_{n+1}&=\sum_{i=0}^{n}C_i\,C_{n-i} \end{align}$

  4. The mergesort runtime recurrence on lists of length $n$:

    $\qquad \begin{align} T(1) &= T(0) = 0 \\ T(n) &= T(\lfloor n/2\rfloor) + T(\lceil n/2\rceil) + n-1 \end{align}$

What are methods to solve recurrence relations? We are looking for

  • general methods and
  • methods for a significant subclass

as well as

  • methods that yield precise solutions and
  • methods that provide (bounds on) asymptotic growth.

This is supposed to become a reference question. Please post one answer per method and provide a general description as well as an illustrative example.

1
source | link