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

Problem Detail: 

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?

Asked By : KXK

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14618

 Ask a Question

 Download Related Notes/Documents