Big O et complexité d'une fonction recursive python

[invite966ef1b5]

Bonsoir,

Je suis actuellement en train d'étudier Big O et la complexite des fonctions et je pense avoir comprit comment cela fonctionne mais j'ai quelques problèmes avec les fonctions récursives.

Prenons l'example de la fonction ci-dessous:

def ajoutBinaire(listeDeNombre):    
assert len(listeDeNombre) > 0
    if len(listeDeNombre) == 1:
        return listeDeNombre[0]
    else:
        return ajoutBinaire(listeDeNombre[:int(len(listeDeNombre)/2)]) + ajoutBinaire(listeDeNombre[int(len(listeDeNombre)/2):])

A chaque execution il y a :

- 4 len qui sont O(1) donc : 4

- une addition qui est O(1) donc : 1

- deux list slice qui sont O(k) et donc ce cas je pense que chaque sont O(n/2) donc : O(n/2) X 2

Donc je pense que le big O est O(2^n) et que T(n) = 2T(n/2) + 2(n/2) + 5

Est-ce que quelqu'un peut me confirmer que c'est juste et que j'ai bien comprit?

Merci d'avance
-----

[invite9dc7b526]

Je ne comprends pas comment tu passes de O(n/2) à O(2^n). Au fait en français on dit "grand o"!

[invite966ef1b5]

Je ne comprends pas comment tu passes de O(n/2) à O(2^n). Au fait en français on dit "grand o"!

Merci Minushabens pour ta réponse.

J'ai juste regarde ce lien qui explique que comme pour l'algorithme de Fibonacci quand la fonction est : return function(...) + function (...) alors c'est O(2^n).

Oú est-ce que je me trompe?