Discussion :

[borisd]

Comme je l'ai dit plus haut, trace l'arbre des appels pour n=8 par exemple et compte les noeuds, tu devrais être d'accord avec moi : son nombre de noeuds est exponentiel par rapport à sa profondeur (2^profondeur) mais sa profondeur est de l'ordre de log2(n). Tu as bien un nombre de noeuds linéaire, multiplié par une constante -> O(n).
Ceci est valable pour l'algorithme que j'ai donné. Si le tiens est différent, je n'ai aucune idée de sa complexité.

[Edit] Je viens de voir ton edit. Je suis plutôt d'accord vu que ça concorde avec ce que je dis depuis le début

[sorry60]

Comme je l'ai dit plus haut, trace l'arbre des appels pour n=8 par exemple et compte les noeuds, tu devrais être d'accord avec moi : son nombre de noeuds est exponentiel par rapport à sa profondeur (2^profondeur) mais sa profondeur est de l'ordre de log2(n). Tu as bien un nombre de noeuds linéaire, multiplié par une constante -> O(n).
Ceci est valable pour l'algorithme que j'ai donné. Si le tiens est différent, je n'ai aucune idée de sa complexité.

As tu lu ma resolution d'equation ? (en Edit)

Car O(2n) et O(n) c'est pareil

[sorry60]

[Edit] Je viens de voir ton edit. Je suis plutôt d'accord vu que ça concorde avec ce que je dis depuis le début

Ok nickel

Edit: oui tu le dis depuis le debut mais je voulais y arriver par moi meme avec une demonstration de ce type

[borisd]

cf mon post précédent
[Edit] les aléas du différé...

[sorry60]

cf mon post précédent

On s'y perd avec tous ces Edits


Merci pour ton aide en tout cas