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

in Algorithms
edited by
There should be base condition in order to stop the recurrence equation. Update it.
thanks.corrected & updated.

1 Answer

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






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


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

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

Related questions

0 votes
1 answer
What is the time complexity of the following recurrence relation and step to derive the same $T(n) = T(\sqrt{n}) + log(logn)$
asked Jan 20, 2019 in Algorithms VikramRB 421 views
3 votes
1 answer
What will be the time complexity for the following recurrence relation? $T(n) = 8\sqrt{n} T(\sqrt{n})+(log n)^{2}$ According to me it is $\Theta (n(logn)^{3})$ . Please confirm.
asked Jun 16, 2017 in Algorithms Ashish Sharma 3 690 views
0 votes
1 answer
T(n) = T(n/4) + T(3n/4) + n How to solve these type of problems? Can I solve this using master theorm by considering X = T(3N/4) +N THEN T(N) = T(N/4) +X CAN WE SOLVE LIKE THIS? PLEASE HELP
asked Jan 4, 2019 in Algorithms Mayankprakash 410 views
0 votes
1 answer
T(n)=5 T ($\frac{n}{2}$+16) + n2 please tell the solution as i m getting confused
asked Nov 18, 2018 in Algorithms LavTheRawkstar 305 views