CODEWITHSUNDEEP
algorithmrecursiontime-complexity
abhi2244
abhi2244

Reputation: 13

Efficient approach for recursive functions

I have given three recursion functions fun1(int ), fun2(int ), fun3(int). All three function depends on each other i.e.

fun1(m) = a * fun2(m-1) - b * fun3(m-1)
fun2(m) = c * fun1(m-1) - d * fun3(m-1)
fun3(m) = e * fun1(m-1) + f * fun2(m-1)

I have to find value for any of these function. How to do it efficiently(in terms of time complexity and non-recursion approach)?

Upvotes: 1

Views: 66

Answers (2)

Paul Hankin
Paul Hankin

Reputation: 58409

You can express your three equations as a matrix multiply:

[f1(m)] = [0 a -b] [f1(m-1)]
[f2(m)] = [c 0 -d] [f2(m-1)]
[f3(m)] = [e f  0] [f3(m-1)]

Then:

[f1(m)] = [0 a -b]^m [f1(0)]
[f2(m)] = [c 0 -d]   [f2(0)]
[f3(m)] = [e f  0]   [f3(0)]

So assuming you know the values of f1(0), f2(0), f3(0), you can compute the values for f1(m), f2(m) and f3(m) in O(log m) arithmetic operations by computing the matrix power using exponentiation by squaring.

Upvotes: 4

Leszek
Leszek

Reputation: 1231

If your coefficients a,b,c,d,e,f don't depend on m, but are absolute constants (or even arbitrary polynomials in variable not depending on m), then the recurrence you describe is called 'linear'. Such case is completely solved by Petkovšek's algorithm.

The algorithm basically lets one compute a so-called closed form of the recurrence. It is described in detail here: https://www.math.upenn.edu/~wilf/AeqB.html

Upvotes: -1

Related Questions