samlai Posted November 1, 2003 Share Posted November 1, 2003 Hi, can someone post a good link or a short tutorial on how to do recurrence problems (question 58 and 67 on practice test) Quote Link to comment Share on other sites More sharing options...
nonevent99 Posted November 1, 2003 Share Posted November 1, 2003 Originally posted by samlai Hi, can someone post a good link or a short tutorial on how to do recurrence problems (question 58 and 67 on practice test) This one is good for simple T(n) = aT(n/b) + f(n) recurrences: http://www.cs.duke.edu/~mlittman/courses/Archive/cps130-97/lectures/lect04/node33.html Here's one for general recurrences: http://www.csee.umbc.edu/~tadwhite/203.s00/recur.pdf The specific T(n) = aT(n/b) + lg(n) type problem is covered in Cormen and Rivest. Any problem with T(n) = T(n-k) + T(n/b) has exponential growth. Any problem with T(n) = T(n-k) + O(n^p) has O(n^(p+1)) growth. Any problem with T(n) = aT(n/b) + O(1) has O(a^lg(n base b)) growth. I think that's right. Please correct me, folks, if this is wrong. Quote Link to comment Share on other sites More sharing options...
CalmLogic Posted September 19, 2007 Share Posted September 19, 2007 An easy way to remember the master theorem is to know the justification: Justification Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.