Corrigé

C'est bien la troisième proposition qui est la bonne !

La troisième ligne de l'algorithme a pour complexité :

En reprenant ce que l'on a fait pour Fibonacci, on a l'inégalité :

$$ C(n) \leq \mathcal{O}(1) + 2 \cdot C(n/2) $$

Ce qui donne en réitérant cette inégalité :

$$ C(n) \leq \mathcal{O}(1)(\sum_{i=0}^K2^i) + 2^K \cdot C(n/2^K) $$

Comme la seule complexité que l'on connait est $C(1) = \mathcal{O}(1)$, on doit prendre $K$ tel que $2^K \simeq n$, c'est à dire $k = \log_2(n)$. On a alors :

$$ C(n) \leq \mathcal{O}(1)(\sum_{i=0}^{\log_2(n)}2^i) + 2^{\log_2(n)} \cdot C(1) $$

Et donc :

$$ C(n) \leq \mathcal{O}(1)(2^{\log_2(n) +1}) + 2^{\log_2(n)} \cdot C(1) $$

Et comme $2^{\log_2(n)} = n$, on trouve bien $C(n) \leq \mathcal{O}(n)$.