I'm not sure the term, but how do you solve a recurrence relation with a multiplicative factor in the index, so as opposed to $a_n=a_{n-1}+a_{n-2}$ we have something like $a_n=a_{\frac{n}{2}}$. I know that it's easy to guess solutions often, but is there a methodological way of doing this, like characteristic polynomials?
Asked
Active
Viewed 153 times
1
-
something like that http://en.wikipedia.org/wiki/Master_theorem? – Snufsan Sep 08 '14 at 18:48
-
Haha, that's actually where my question came from. That just gives run times, doesn't it? – Sep 08 '14 at 19:25
-
But it's give you a great way to solve reccurence – Snufsan Sep 08 '14 at 20:04
-
1In recurrences with $a_{\lfloor n / b \rfloor}$ on the right hand side, it is often enlightening to consider the special case when $n = b^k$ and generalize from there. – A.E Sep 08 '14 at 21:43