1
$\begingroup$

How does one convert a recurrence relation to a non-recursive function?

I am not sure about the substitution, recursion tree, and master method. Is there an easy way to do this?

  • 3
    For some recurrence relations this is very easy; for some it is very hard. What recurrence are you interested in, and what havce you tried?2011-03-24
  • 1
    Just to give a general idea, you may want to check out Wilf's Generatingfunctionology at http://www.math.upenn.edu/~wilf/DownldGF.html. Are you talking about the master theorom in computer science, by any chance?2011-03-24
  • 0
    If you are referring to the methods in this [MIT lecture](http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-2-asymptotic-notation-recurrences-substitution-master-method/) and [notes](http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-2-asymptotic-notation-recurrences-substitution-master-method/lec2.pdf) then the way to learn (as with most algorithms) is practice, initially following the book or notes.2011-03-24
  • 0
    Please make your posts self-contained; the body should have all the information necessary to understand them, not relying on the title for important information.2011-03-25

1 Answers 1

1

The master method applies only in some situations (see the link); when it does apply, it tells you what you'll get if you use the recursion tree method.

The substitution method works especially well for recursions like $$ f(n) = f(n-1) + g(n), \quad f(n) = f(n/2) + g(n), $$ and in any other situation in which $f(n)$ depends on at most one earlier value of $f$. In some cases you can look up the answer. For example, there is the "polynomial method", which is a recipe for solving recurrences of the type $$ f(n) = \begin{cases} f(n-1) + P(n) & n > n_0, \\ C & n = n_0. \end{cases} $$ For example, if you define $f(0) = 0$ and $f(n) = f(n-1) + 2n - 1$ then you get using this method that $$ f(n) = n^2. $$ A vast generalization is Gosper's algorithm, see also A=B.