Théorème maître : applications

Difficile

Appliquer le théorème maître pour déterminer la complexité des récurrences suivantes :

T(n) = 4 \, T(n/2) + O(n)

T(n) = 2 \, T(n/2) + O(n \log n)

T(n) = 3 \, T(n/3) + O(n)

T(n) = T(n/2) + O(n)

Pour chacune, identifier $a$ , $b$ , $d$ et le cas du théorème maître qui s'applique.

La solution est réservée aux abonnés

L'énoncé est en libre accès. Les indices progressifs et la solution détaillée sont réservés aux abonnés Premium.

Théorème maître : applications

Difficile

Appliquer le théorème maître pour déterminer la complexité des récurrences suivantes :

T(n) = 4 \, T(n/2) + O(n)

T(n) = 2 \, T(n/2) + O(n \log n)

T(n) = 3 \, T(n/3) + O(n)

T(n) = T(n/2) + O(n)

Pour chacune, identifier $a$ , $b$ , $d$ et le cas du théorème maître qui s'applique.

L'énoncé est en libre accès. Les indices progressifs et la solution détaillée sont réservés aux abonnés Premium.