Analisi algoritmo ricorsivo

Salve, ho difficoltà a risolvere il costo asintotico della funzione f() del seguente algoritmo

Codice:

static int f(int q) {
if(q <= 1) return q;
if((q % 2) == 0) return g(q>>1);
else return f(q-1);
}
static int g(int r) {
if(r <= 1) return f(r);
if((r % 3) == 0) return f(r/3);
else return f(r+1);
}

Ho pensato che il caso peggiore è quello in cui q>>1 non è mai divisibile per 3 e che il numero di chiamate di g siano logaritmiche in funzione di q, ma non riesco ad andare avanti.Qualcuno potrebbe spiegarmi come ci si muove quando mi trovo davanti ad algoritmi simili?
Grazie per le eventuali risposte

Di solito avere due funzioni è abbastanza scomodo ed è meglio riportarsi ad una sola. In questo caso hai che \(f(q) = g\bigl( \lfloor q/2 \rfloor \bigr)\) usando il fatto che se \(q\) è pari \( \lfloor q/2 \rfloor = q/2, \) e se è dispari allora \( q - 1 \) sarà pari e \( \lfloor q/2 \rfloor = (q - 1)/2. \) Puoi a questo punto sostituire questa funzione al posto di \(f\) nella \(g\) ottenendo
\[
g(r) =
\begin{cases}
r & \text{ se } r \leq 1 \\
g\left( \left\lfloor \frac{r/3}{2} \right\rfloor \right) = g \bigl( \lfloor r/6 \rfloor \bigr) & \text{ se $r$ divisibile per $3$} \\
g\left( \left\lfloor \frac{r + 1}{2} \right\rfloor \right) = g \bigl( \operatorname{rpi}(r/2) \bigr) & \text{altrimenti}
\end{cases}
\]
dove \( \operatorname{rpi} \) è la funzione che arrotonda all'intero più vicino (con il valore intermedio che va all'intero più grande). Per la funzione \(g\) il caso peggiore è quindi quello in cui non hai mai un numero divisibile per \(3\) e la funzione verrà eseguita \( log_2(r) \) volte. Nel caso migliore verrà eseguita solo \( \log_6(r) \) volte. Nota comunque che da punto di vista della complessità asintotica tutti i logaritmi sono uguali.. Differiscono infatti da una costante positiva come si può vedere usando il cambiamento di base dei logaritmi. Per cui alla fine la differenza non è così grossa.