Développement : Master Theorem

Détails/Enoncé :

En analyse de la complexité des algorithmes, on est souvent dans le cas d'un algorithme dont la complexité $C(n)$ vérifie
\[
C(n) = a C(n/b) + f(n)
\]

Le "master theorem" étudie le comportement asymptotique de $C(n)$ de manière générale.


La preuve est calculatoire mais donne un résultat intéressant.

Recasages pour l'année 2024 :

Références utilisées dans les versions de ce développement :

Introduction à l'algorithmique, Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest (utilisée dans 49 versions au total)