Сложность времени этого взаимно-рекурсивного кода

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); 
} 

Answer 1

Вы можете переписать G в терминах F.

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

Это позволяет переписать F в терминах F.

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

Результат O (п): O (F (n)) для случая, когда n% 2 == 0 - log (n), что означает, что O (F (n)), когда n% 2! = 0 является O (n) + O (log (n)) или просто O (n)