Disclaimer : je n'y connais pas grand chose en complexité.
En considérant le pseudo-code suivant, qui a AFAIK le même comportement que la fonction de l'OP :
def f(n, m):
if c1(n, m):
return n, m
first_call = f(decay(n), m)
second_call = f(decay(n), decay(m)) if c2(m) else default_m_and_n
return first_call if c3(first_call, second_call) else second_call
Qui peut, par exemple, être instanciée comme suit :
def f(n, m):
if n < m:
return n, m
first_call = f(n-1, m)
second_call = second_call = f(n-1, m+n) if m % 2 == 0 else 1, 0
return first_call if second_call[1] < first_call[1] else second_call
Ici, on voit bien qu'un appel de la fonction déclenche 2 appels (1 dans le cas où c2
n'est pas vérifiée).
L'ordre de grandeur de la complexité temporelle est donc O(2^n)
, autrement dit exponentielle.
Maintenant, pour être plus précis, ça dépend beaucoup des conditions. Si c1
est du style n < 0
, on est en exponentiel. Si il dépends de m et de n, c'est plus compliqué, puisqu'on peut avoir des branches entières qui se coupent, et qui de fait peuvent casser la complexité.
De la même manière, si c2
est souvent fausse, la complexité tombe en linéaire puisqu'un appel de fonction ne mène en général qu'à un seul autre appel.
La fonction de l'OP semble tomber dans le cas exponentiel, puisque jour doit atteindre une valeur qui n'est jamais modifiée durant l'exécution de la fonction.