# time complexity to solve recurrence relation

964 views

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

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

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
2

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 ?

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?
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).
0
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?
0
0
actually generating function helps here
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?
0

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

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.
0
Generally k is a finite constant
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))$
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
ok boss :)
0
:) :)
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
Yes I wanted to know if those kinds of recurrences are valid.
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 :) .

## Related questions

1
421 views
What is the time complexity of the following recurrence relation and step to derive the same $T(n) = T(\sqrt{n}) + log(logn)$
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.
T(n)=5 T ($\frac{n}{2}$+16) + n2 please tell the solution as i m getting confused
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://gateoverflow.in/62795/time-complexity-to-solve-recurrence-relation?show=65108", "fetch_time": 1611044479000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2021-04/segments/1610703518201.29/warc/CC-MAIN-20210119072933-20210119102933-00640.warc.gz", "warc_record_offset": 368181857, "warc_record_length": 20076, "token_count": 1715, "char_count": 5378, "score": 3.890625, "int_score": 4, "crawl": "CC-MAIN-2021-04", "snapshot_type": "latest", "language": "en", "language_score": 0.6420020461082458, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00031-of-00064.parquet"}