java - この相互再帰コードの時間計算量

Question

私はJavaでこの相互再帰コードを持っています.このコードの時間の複雑さは何ですか. 私の推測では O(2^n) ですが、G メソッドの場合、 return (n-1) + G(n-1) は呼び出しごとに 2 つに分割されるため、この部分は O(n) ですか? これについてはよくわかりません。

public static int F(int n)
{
    if (n <= 1)
        return 1;
    else if (n % 2 == 0)
        return n + F(n/2);
    else
        return G(n-1)-n;
}

public static int G(int n)
{
    if(n <= 1)
        return 1;
    else if (n % 2 == 0)
        return F(n-1) + G(n-1);
    else
        return F(n-3);
}