0

Given positive real constants $a$ and $b$ with $a < b$, I want to solve the following recurrence relation:

$T(n_{<b}) = 1$

$T(n_{\geq b}) = T(n-a) + T(n-b)$

I expect an answer in the sense of $T(n) = \Theta(c^n)$ where $c$ is given in terms of $a$ and $b$.

Application

For some constant $z$ I have a brute-force algorithm of the form $T(n) = 2(T(n-z))$ which takes time $O(2^{n/z})$. However, I can manage to imbalance the search tree so that it becomes the recurrence of this question with $a < z < b$ which is hopefully faster, although unfortunately I also have $a + b \geq 2z$

vitamin d
  • 5,783
Albert Hendriks
  • 333
  • 1
    If $a,b$ are integers, that is certain what you get, where $c$ is the root $z$ with the largest value $|z|$ of $x^{b}-x^{b-a}-1.$ – Thomas Andrews Jun 22 '21 at 20:52
  • When $r=|z|\geq 2,$ then $$|z|^b>|z^a|+1\geq |z^{b-a}+1|, $$so all to roots of $x^b-x^{b-a}-1$ have modulus $<2,$ which is what you want. But that only for $a,b$ integers. – Thomas Andrews Jun 22 '21 at 21:06
  • If $b=2a$ then the large roots are all of absolute value $$\left(\frac{1+\sqrt{5}}{2}\right)^{1/a}$$ – Thomas Andrews Jun 22 '21 at 21:14
  • Your formula from the first comment seems to work, e.g. a = 1 and b = 3.184 gives c=1.45 which seems realistic in my application. https://www.wolframalpha.com/input/?i=x%5E3.184+-+%28x%5E%282.184%29%29+%3D+1+solve+for+x @ThomasAndrews My bruteforce value for z was 1.84 which gave $c = 2^{1/z} = 1.46$. Then the imbalance gives a tiny speedup. – Albert Hendriks Jun 22 '21 at 21:27

0 Answers0