Optimize a linear recurrence

Question

$$\begin{align*} T[1] &= 1 \\ T[2] &= 2 \\ T[i] &= T[i-1] + T[i-3] + T[i-4] & \text{for \(i \gt 2\)} \\ \end{align*}$$

I have to calculate $T[N]$, but $N$ is too big ($\approx 10^9$), how can I optimize it?

Answer 1

As Bartek commented, you are missing a base case. You can compute large values of $T$ in several ways:

• Bartek's suggestion: Use an array to store all the entries computed so far.
• You can optimize the previous method, dramatically reducing the memory needed: store only the last $4$ entries of the array at each point in time.
• Use matrix powering. There are vectors $x,y$ and a matrix $A$ such that $T[N] = x'A^N y$. This approach is very similar to the previous one.
• Find an explicit solution to your recurrence $T[N] = \sum_{i=1}^4 c_i \lambda_i^n$ (there are other possible forms, but this is the most probable), and use this formula to calculate $T[N]$ directly.

Answer 2

Imagine your solution now is Gn = Gn-1 + Gn-2 + Gn-3

The solution just changes to

[ Gn Gn-1 Gn-2 ] = [ Gn-1 Gn-2 Gn-3 ] [ 1 1 0 ]
                                      [ 1 0 1 ]
                                      [ 1 0 0 ]

Similarly

[ Gn-1 Gn-2 Gn-3 ] = [ Gn-2 Gn-3 Gn-4 ] [ 1 1 0 ]
                                        [ 1 0 1 ]
                                        [ 1 0 0 ]

So finally,

[ Gn Gn-1 Gn-2 ] = [ G3 G2 G1 ] [ 1 1 0 ] ^n-3
                                [ 1 0 1 ]
                                [ 1 0 0 ]

Calculating power of a matrix, $$M^n$$ can be done in O(log n).

For your case, the Matrix will be

[ Gn Gn-1 Gn-2 Gn-3] = [ Gn-1 Gn-2 Gn-3 Gn-4 ] [ 1 1 0 0]
                                               [ 0 0 1 0]
                                               [ 1 0 0 1]
                                               [ 1 0 0 0]

Answer 3

There aren't enough initial values, but still. Define: $$ A(z) = \sum_{n \ge 0} T[n] z^n $$ Properties of ordinary generating functions give for the recurrence: $$ T[n + 4] = T[n + 3] + T[n + 1] + T[n] $$ $$ \frac{A(z) - T[0] - T[1] z - T[2] z^2 - T[3] z^3}{z^4} = \frac{A(z) - T[0] - T[1] z - T[2] z^2}{z^3} + \frac{A(z) - T[0]}{z} + A(z) $$ This finally leads to form: $$ A(z) = \frac{p(z)}{z^4 - z^3 - z - 1} = \frac{A_1}{1 - \phi z} + \frac{A_2}{1 - \overline{\phi} z} + \frac{B z + C}{1 + z^2} $$ Here $A_1$, $A_2$, $B$ and $C$ are constants depending on the initial $T$ values, and $$ \begin{align*} \phi &= \frac{1 + \sqrt{5}}{2} \\ \overline{\phi} &= 1 - \phi = - \frac{\sqrt{5} - 1}{2} \end{align*} $$ The first two are geometric series, the last one adds terms alternating between 0 and 1 to the solution. And as $\lvert \overline{\phi} \rvert \approx 0.618$ while $\phi \approx 1.618$, the first term dominates. The value at large $n$ is approximately $T[n] \approx A_1 \phi^n$.