I have a recurrence relation,
$ a_n = a_{n-1} + a_{n-2} + a_{n-3} + 2^{n-3} $ for $n>3$ and $a_1 = 0, a_2 = 0, a_3 = 1$
I have to find the value of $a_n$ for very large values of n. I tried an approach similar to that which we use for finding the fibonacci numbers using matrix method which gives us $f_n$ in $log(n)$ time complexity. But I am not able to use it here because of the $2^{n-3}$ term.
Can we do better than $O(n)$ time complexity.