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

OK ! Thanks.

I think what you have calculated a simplified closed form of value given by the recurrence relation.

[given recurrence relation F(n) is not for time complexity]

example : $F_n=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n- \frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n$ for the fibonacci recurrence relation which depends on two previous terms. Here although F(n) grows exponentially, we know that if we use memoization or bottom up dp we can achive a linear time complexity to calculate F(n).

Additionaly : If we use matrix exponentiation like below,

$\left[ \begin{matrix} 1 && 1 \\ 1 && 0 \end{matrix} \right]^n = \left[ \begin{matrix} F(n+1) && F(n) \\ F(n) && F(n-1) \end{matrix} \right]$

Then T(n) for F(n) becomes $O(\log n)$

So my point is, What is the best time complexity we can achive to solve such a generic recurrence relation depending on k previous terms ? What if such questions asked in exam without specifying any algorithm ?

---

yes for fibonacci number it will be O(n)

where $c_{1}=\frac{1}{\sqrt{5}} c_{2}=-\frac{1}{\sqrt{5}}$

and r=$\left ( \frac{1\pm \sqrt{5}}{2} \right )$

 

but for matrix  it will be n terms summation rt?

then how it will be log n?

---

$\left[ \begin{matrix} 1 && 1 \\ 1 && 0 \end{matrix} \right]^n = \left[ \begin{matrix} F(n+1) && F(n) \\ F(n) && F(n-1) \end{matrix} \right]$

Using this we can calculate F(n) . We can create a matrix F[2][2] and initialize with {{1,1},{1,0}}, and calculate the powers (exponentiate ) of it using divide and conquer which takes $\log n$ if the qeury is F(n).

---

Answer should be O(n)

---

F(n)=$\left[ \begin{matrix} 1 && 1 \\ 1 && 0 \end{matrix} \right]^n$

= $\left[ \begin{matrix} n && n \\ n && 0 \end{matrix} \right] $

Now solving is possible in simplified form, rt?

---

http://fusharblog.com/solving-linear-recurrence-for-programming-contest/#printSource

---

actually generating function helps here

---

yes here they are getting (log n) complexity because they are squaring each time

but in this matrix no need to do squaring each time rt?

---

@ Uddipto are you referring to closed form calculation using generating function ?

---

@Debashsish. The link which you have posted says the time complexity is Big-O($k^3.logn$). Its not Big-O($logn$). Requesting you to check once again and correct me if I am wrong.

@srestha. The closed form says that the solution is of the form:

$c1.{(root1)}^n + c2.{(root2)}^n...+...$    in general.

Computing  ${(root)}^n$ takes Big-O($logn$) time. Now, if degree of the recurrance relation is 'd'(and so it would have maximum of 'd' roots), the time complexity to compute F(n) is Big-O($d.logn$)

Thus, time complexity is Big-O($n.logn$) + additional complexity to compute the roots of the polynomial.

---

Generally k is a finite constant

---

No, 'k' is degree of the recurrance relation. It can even extend to 'n'. For example,

Consider that F(n) is summation of all the previous terms from $(n - 1)$ to $0$. So, in such a situation,

$k = n$.

That would result to $O(n^{3}.log(n))$

---

I am aware of that fact. For that given relation k is a constant. But what my point was, k is small compared to n. in most of the possible cases. It's not like that you are increasing n and simultaneously increases k to n. Its mathematically feasible but, you might have seen in the link how they have multiplied two matrices,it's hardly of 4 to 5 degree.

---

ok boss :)

---

:) :) 

---

How to define a recurrence where $n$th term depends on previous n terms? Shouldn't $k$ be a constant independent of $n$?

---

@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 :) .