Recurrence Relations [closed]

Question

How to calculate tribonacci number for very large n ( say 10^14 ) in best complexity. Tribonacci numbers are defined as F(n)=F(n-1)+F(n-2)+F(n-3) with F0=1, F1=2, F2=4.

Or recurrence defined as F(n)=aF(n-1)+bF(n-2)+cF(n-3) with F0=1, F1=2, F2=4.

I want to Calculate nth term in log(n) just like nth Fibonacci number.

How can I generate the Base Matrix for using matrix exponentiation to calulate the nth term?

Previously I was trying to implement it using DP but as we cannot take array of such large size its not working fine. Similarly Recursion didn't work here due to stack overflow for very large numbers of order of 10^14.

Answer 1

The best asymptotic complexity for tribonacci numbers will be using a matrix exponentiation method like the one for Fibonacci numbers. Specifically, written correctly, this is O(log n) integer operations, rather than O(n) (like the dynamic programming method) or O(3ⁿ) (like the naive solution).

The matrix of interest is

    [1, 1, 1]
M = [1, 0, 0]
    [0, 1, 0]

and the nth tribonacci number is in the upper left corner of Mⁿ. The matrix exponentiation must be computed by squaring to achieve log(n) complexity.

(for F(n+3) = a F(n+2) + b F(n+1) + c F(n), the matrix is:

    [a, b, c]
M = [1, 0, 0]
    [0, 1, 0]

and the result is {F_n+2,F_n+1,F_n} = Mⁿ {F₂,F₁,F₀}, also see here.)