edited by
2,447 views
3 votes
3 votes

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)$

edited by

1 Answer

1 votes
1 votes
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

Related questions

1 votes
1 votes
1 answer
1
VikramRB asked Jan 20, 2019
1,005 views
What is the time complexity of the following recurrence relation and step to derive the same$T(n) = T(\sqrt{n}) + log(logn)$
1 votes
1 votes
1 answer
4