[exo] complexité d'un algorithme récursif

[qwerty azerty]

Bonjour je travaille sur un exercice qui consiste à déterminer la complexité T(n) d'un algorithme récursif suivant :

f(n) :
| if n > 0 then:
| | f (n − 1)
| | f (n − 1)
| else:
| | OPERATION(n)

on considère que OPERATION(n) a une complexité constante.

Je sais que je doit d'abord déterminer une relation de récurrence de T(n). Pour le cas n <= 0, T(n) = 1 jusque là tout vas bien. Par contre pour le cas ou n > 0 je ne sais pas si T(n) = 2T(n-1) ou T(n) = 2T(n-1)+1. Est ce que je dois considérer OPERATION(n) également dans le deuxième cas car la fonction finira toujours par "atteindre" le cas de base?

Mercis d'avance à celui ou celle qui m'aiderais.
-----

[MissJenny]

essaie de voir ce qui se passe pour n=1 puis n=2.

[qwerty azerty]

Merci de votre réponse.
Avec n = 2 j'ai 6 appels récursifs et avec n = 1 j'en ai 2. T(n) = 2T(n-1) + 1 signifie que j'ai un nombre impaire d'appels, ce qui n'est pas le cas. Donc pour n> 0, T(n) = 2T(n-1).
Merci beaucoup et bonne journée.

[pm42]

Le +1 de l'opération constante ne va pas contribuer à la complexité.
Tu peux faire le calcul avec tes 2 relations de récurrence, tu arriveras au même résultat final pour le terme dominant.

[A voir en vidéo sur Futura]

[qwerty azerty]

Oui en effet j'ai testé et j'obtient le même résultat. Mercis du temps que vous m'avez consacré et bonne journée.