How to calculate or estimate how long it takes to solve a recurrence relation?

Question

I am trying to understand how to solve complex recurrence relations and whether there is a general method or technique to help me. That being said I am not talking about recurrence relations that can be solved using the (generalized) Master Theorem or the Akra–Bazzi method.

This is by no means a "I have some homework to solve, please solve it for me" question. It is more at a conceptual level. I want to be able to solve and "see" through these relations with ease.

How do you efficiently calculate the time needed to solve a recurrence relation?

Is it something that, simply put, takes experience and personal intuition? Is there some cannon method that I am not aware of? Moreover, how do you go on to calculate the same relations for cases where you have memoization?

Answer 1

There are at least three questions here:

1. How does one solve a recurrence relation on paper?
2. How does one efficiently calculate a sequence given by a recurrence relation, say using memoization?
3. Given a recurrence relation, can one predict the running time of the best method for computing it?

Let me answer them one by one. For the first question, this is a particular instance of the classical question, how to solve problems. Consider the (finite!) recurrence relation given by $$ \gamma_0 = 1, \quad \gamma_{m+1} = E, \quad \ell\gamma_{\ell+1} = (2\ell-m+c-1)\gamma_\ell + (m-\ell+1)\gamma_{\ell-1} (1 \leq \ell \leq m). $$ (The sequence is $\gamma_0,\ldots,\gamma_{m+1}$, and $E,c$ are parameters.) What is the solution of this recurrence? If you're interested, have a look at the top of page 7 in this paper, which unfortunately doesn't explain how the authors found the explicit formula; Mathematica manages to solve this recurrence somehow. For some general methods useful for solving recurrence relations, consult our reference question.

For the second question, we can consider a very general class of recurrence relations which produce a sequence $(\gamma_i)_{i \in \mathbb{N}}$ by giving each $\gamma_i$ in terms of values $\gamma_j$ for $j < i$. Such recurrences can be efficiently computed using memoization. The time required to compute $\gamma_n$ is upper-bounded by $n$ multiplied the time it takes to calculate the defining formula of $\gamma_i$. This bound can be tricky to evaluate, since the time needed to carry arithmetic operations depends on the size of the operands, which could grow rather fast depending on the recurrence (consider for example $\gamma_0 = 1$, $\gamma_n = n\gamma_{n-1}$).

For the third question, it is easy to artificially reduce the halting problem to my statement of the problem, so in general it is hard to predict the best running time. But one can probably predict (or at least upper-bound) the running time of memoization. Given my answer to the previous question, all you need is to somehow bound the size of the elements of the sequence. In many cases one can get reasonable bounds, for example this is probably possible for recurrence relations in which $\gamma_n$ depends polynomially on $n$ and $\gamma_{n-1},\ldots,\gamma_{n-c}$ for some finite $c$. While you shouldn't expect to get tight bounds this way, for a "generic" recurrence relations, one can probably predict the order of growth.

Answer 2

There is no general way to solve all recurrence relations, however, there is a general way to solve all homogeneous linear recurrence relations exactly by employing linear algebra.

The idea is as follows: 1) For a linear recurrence relation of size $k$, e.g. $a_n = c_1 a_{n-1} + c_2 a_{n-2} + ... + c_k a_{n-k}$, write down $k$ consecutive iterations from $n-k$ to $n$.

2) Transform the set of $k$ equations into a matrix-vector form of dimension $k$. The $n$-steps of the addition of the linear recurrence combined with the $k$-dimensional vector of initial values will become a recurrence of an $n$-step $k \times k$-dimensional matrix multiplication followed by one last matrix-vector multiplication on the right side with the initial vector.

3) rewrite the $n$-step matrix multiplication of $A$ into $A^n$

4) diagonalize the matrix $A$ into three matrices: $A = TDT^{-1}$ of which $D$ is a diagonal matrix and $T$ is regular. In some corner cases, $A$ might not have a diagonalized form, in which case one should attempt to find the (more general) Jordan normal form of $A$ instead. 4.1) This means one need to find all eigenvalues $\Lambda$ and their corresponding eigenvectors $V$ of $A$. 4.1.1) One need to find all roots of the characteristic polynomial of $A$ to get its eigenvectors and corresponding eigenvalues.

Note that $D$ can easily be expressed in a closed form depending on $A$'s eigenvalues $\lambda_1 ... \lambda_k$, and both of $T$ and $T^{-1}$ can easily be expressed in a closed form depending on its eigenvectors $v_1 ... v_k$. At this point I would recommend to drop the parameters $c_1 ... c_k$ from the equation and abstract them away using the above $\Lambda_i$ and $v_i$ for readability.

5) now rewrite $A^n$ into $(TDT^{-1})^n = T D^n T^-1$. Note that $D^n$ can easily be computed from $D$, since it is diagonal.

6) figure out an easy way to formally multiply this equation out. I recommend leaving the vector of initial values out until the very end. When finally computing $A^n * b$, note that one only need the last row of the resulting product, meaning one can leave out all others.

7) Depending on what one intend to do with the recurrence relation, it may be time to substitue $c_1 ... c_k$ back into the eigenvalues and eigenvectors.

8) The resulting equation gives $a_n$ explicitly depending only on the initial values $a_0, a_1 ... a_{k-1}$ and either $c_1, c_2 ... c_k$ or $\lambda_1 ... \lambda_k$ and $v_1 ... v_k$.

These results can be generalized for linear recurrences with affine components of n added (functions depending only on n), and even further for small polynomial, exponential and some other components depending only on n. However, it's not possible to generalize this explicit closed formula for linear recurrences for arbitrary functions depending only on n, because doing so would require a closed explicit form for arbitrary series given its sequence function, and AFAIK that's impossible.

As soon as recurrences with more than one operand are generalized from linear to polynomial recurrences, things become very complicated. Even if we allow only quadratic recurrences of a single step, things are already complicated and there are almost no non-trivial exact solutions (only a countable infinite subset out of the uncountable infinite parameter space actually do have closed forms). One neat example is $a_n = 2*a_{n-1}^2 - 1 = \cos(2^n \arccos(a_0))$, which comes from the double angle cosine law. Generally, for finding one of those sparse explicit solutions to general polynomial recurrence relations, one have to consider Fourier theory and keep track of repetitions, which can be done using functional properties of trigonometric or polynomials of exponential functions.

If one generalize even further, all bets are off. If you need a numerical result of one of those hard cases, the best thing one can do is trying to guess some upper and lower bound, which is usually done by ignoring all but the most significant parts of any term.

Also, recurrence relations are closely related to generating functions.

This is a subject where one can talk more than this site can take.