time complexity to solve recurrence relation

Question

recurrence relation for the functional value of F(n) is given below :

$F(n) = a_{1}F(n-1) + a_{2}F(n-2) + a_{3}F(n-3) + \ldots + a_{k}F(n-k)$  

where $a_{i} =$ non zero constant.

Best time complexity to compute F(n) ?

assume k base values starting from F(0), F(1), to F(k-1) as $b_{0} , \ b_{1} \ , b_{2} \ .... \ b_{k-1}$ ; $b_{i} \neq 0$

A. Exponential ( $O(k_{2}r^{k_{1}n})$) 

B. Linear ( $O(n)$ )

C. Logarithmic ( $O(\log n)$ )

D. $O(n \log n)$

Comments

There should be base condition in order to stop the recurrence equation. Update it.

---

thanks.corrected & updated.

Answer 1

Removing constant terms $a_{1},a_{2}...................$

$F(n)=F(n-1)+F(n-2)+.................F(1)$

       =$F(n-1)=cr^{n-1}$

       =$F(n-2)=cr^{n-2}$

        $--------------------------$

 

So, $cr^{n-1}+cr^{n-2}+.................+cr^0=0$

$F(n)=\frac{r^{n-1}-1}{r-1}$

Complexity will be $O(r^{n-1})$ where r is a constant

Comments

@air1. We have been solving recurrances of the type where 'k' was constant. But I doubt if this is mandatory.

---

Yes I wanted to know if those kinds of recurrences are valid.

---

@air1. Consider the sequence,

f(n) = 2.f(n -1)

      = f(n - 1) + f( n - 1)

Now, if we expand $2^{nd}$ f(n - 1), then we get previous terms. If we repeat the procedure of expanding only $2^{nd}$ terms, then we get
f(n) = f( n - 1 ) + f( n - 2 ) + f( n - 3 ) + f( n - 4 ) .........2.f(0).

Even though this is indirect expansion, I think we can have such recurrances. I havent studied higher mathematics :) .