  We study the growth behaviour of rational linear recurrence sequences. We
show that for low-order sequences, divergence is decidable in polynomial time.
We also exhibit a polynomial-time algorithm which takes as input a divergent
rational linear recurrence sequence and computes effective fine-grained lower
bounds on the growth rate of the sequence.

Computational Complexity;Discrete Mathematics