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