[Solved]: How to calculate or estimate how long it takes to solve a recurrence relation?

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 ellgamma_{ell+1} = (2ell-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 = ngamma_{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.