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

1 vote

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

$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

2

OK ! Thanks.

I think what you have calculated a simplified *closed form* of 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 ?

0

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?

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?

0

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

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

0

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?

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

Now solving is possible in simplified form, rt?

0

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?

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

0

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

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

0

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

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

0

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.

0

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

1

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

0

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

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