Réseau Graphes P. Fonctionnelle P. Logique Complexité

L3

Complexité - Fiche de TD n°4

Exercice 3

1. T(n) = 2 * T(n/2) + n

Rappel: Théorème de la méthode générale:

T(n) = a * T(n / b) + f(n)

Ici on a, a = 2, b = 2, f(n) = n.

De plus, on a:

n^log_b(a) = n^log₂(2) = n = f(n)

On est donc dans le cas n°1. D'où:

T(n) = O(n^log_b(a) * log₂(n))