Calculating complexity for recursive algorithm with codependent relations

Question

I wrote a program recently which was based on a recursive algorithm, solving for the number of ways to tile a 3xn board with 2x1 dominoes:

F(n) = F(n-2) + 2*G(n-1)

G(n) = G(n-2) + F(n-1)

F(0) = 1, F(1) = 0, G(0) = 0, G(1) = 1

I tried to calculate the complexity using methods I know such as recursion tree and expansion, but none resulted in any answer. Actually I had never come across such a recursion, where the relations are codependent.

Am I using the wrong methods, or maybe using the methods in a wrong way? And if so, can anyone offer a solution?

Edit: I asked the same question in CS Stack Exchange, and a good answer was also given there. https://cs.stackexchange.com/questions/124514/calculating-complexity-for-recursive-algorithm-with-codependent-relations

You might try asking over on the CS Stack Exchange as they're better equipped to tackle theoretical questions. See also: Which computer science / programming Stack Exchange sites do I post on? — John Kugelman
– John Kugelman, Commented Apr 21, 2020 at 17:20

btilly · Accepted Answer · 2020-04-21 20:59:14Z

It is exponential. All that is left to do is to find the base. First define a vector valued function V(n) as follows.

       ( F(n)   )
V(n) = ( F(n-1) )
       ( G(n)   )
       ( G(n-1) )

And now we have V(n) = A * V(n-1) where A is some matrix. If I didn't mess it up, that matrix is:

[ 0 1 2 0 ]
[ 1 0 0 0 ]
[ 1 0 0 1 ]
[ 0 0 1 0 ]

From your initial conditions:

       ( 1 )
V(1) = ( 0 )
       ( 1 )
       ( 0 )

And now we have the following rule. V(n+1) = A^n * V(1). If you're familiar with matrix math, the growth of this exponential is dominated by the leading eigenvalue. Which (after checking https://www.dcode.fr/matrix-eigenvalues) happens to be sqrt(2+sqrt(3)).

So F(n) = O(sqrt(2+sqrt(3))^n).

(The theory behind this is usually explained with the Fibonacci sequence, but it can be applied for any difference equation.)

Collectives™ on Stack Overflow

Calculating complexity for recursive algorithm with codependent relations

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related