Aicirt
09-07-2005, 06:53 PM
Im taking a graduate algorithms course without first taking an undergrad course. The prof assumes that we know a few concepts that I have not recieved and Im just a bit slow to pick up on some of these concepts. I was wondering if someone who has solved some recurrences in the past would be able to help me out with this. I understand how to solve them when I can apply the master theorm to the reccurence, but when it does not apply, I get stuck. Take for instance the following example:
T(n) = ( sqrt(n) ) * T(sqrt(n)) + n
Since the coefficient a, where T(n) = aT(n/b) + f(n), is not a constant, the master therom does not apply. I believe that there is some sort of transformation that I am supposed to do however Im not exactly sure how to do this. Also every single recurrence example in my text book uses constants for the a value. Anyone help get me started in the right direction?
Aicirt
T(n) = ( sqrt(n) ) * T(sqrt(n)) + n
Since the coefficient a, where T(n) = aT(n/b) + f(n), is not a constant, the master therom does not apply. I believe that there is some sort of transformation that I am supposed to do however Im not exactly sure how to do this. Also every single recurrence example in my text book uses constants for the a value. Anyone help get me started in the right direction?
Aicirt