Calculating complexity for recursive algorithm with codependent relations
Let us note that $F(n) = G(n+1) - G(n-1)$. Therefore
$$
G(n+1)-G(n-1) = G(n-1) - G(n-3) + 2G(n-1),
$$
implying that
$$
G(n+1) = 4G(n-1) - G(n-3).
$$

Similarly, $G(n) = (F(n+1)-F(n-1))/2$, and so
$$
(F(n+1)-F(n-1))/2 = (F(n-1)-F(n-3))/2 + F(n-1),
$$
implying that
$$
F(n+1) = 4F(n-1) - F(n-3).
$$
These are exactly the same recurrences, though with different initial values.

A simple induction shows that $F(n) = 0$ for odd $n$ while $G(n) = 0$ for even $n$ (this also follows from their semantic meaning).

Using the recurrence, we easily get that for even $n$,
$$
F(n) = (1/2 + 1/2\sqrt{3})(2 + \sqrt{3})^{n/2} + (1/2 - 1/2\sqrt{3})(2 - \sqrt{3})^{n/2}.
$$
Let us comment that this sequence is A001835.

Similarly, for odd $n$,
$$
G(n) = (1/2 + 1/\sqrt{3})(2 + \sqrt{3})^{(n-1)/2} + (1/2 - 1/\sqrt{3})(2 - \sqrt{3})^{(n-1)/2}.
$$
This sequence is A001353.



Alternatively, we can notice that
$$
\begin{pmatrix}
F(n) \\
G(n+1)
\end{pmatrix} =
\begin{pmatrix}
1 &amp; 2 \\
1 &amp; 3
\end{pmatrix}
\begin{pmatrix}
F(n-2) \\
G(n-1)
\end{pmatrix}
$$
It follows that
$$
\begin{pmatrix}
F(2m) \\
G(2m+1)
\end{pmatrix} =
\begin{pmatrix}
1 &amp; 2 \\
1 &amp; 3
\end{pmatrix}^m
\begin{pmatrix}
1 \\
1
\end{pmatrix}
$$
The eigenvalues of the matrix are $2 \pm \sqrt{3}$, and so we are led to formulas as stated above.