Master theorem

En informatique, et plus particulièrement en analyse de la complexité des algorithmes, le master theorem ou théorème sur les récurrences de partition permet d'obtenir une solution en termes asymptotiques (en utilisant les notations en O) pour des relations de récurrence d'un certain type rencontrées dans l'analyse de complexité d'algorithmes qui sont régis par le paradigme diviser pour régner. L'énoncé sur les expressions asymptotiques de ces récurrences a été nommé « master theorem » dans la version anglaise du manuel Introduction to Algorithms de Cormen, Leiserson, Rivest et Stein; dans sa traduction française, le théorème est appelé le « théorème général ». L'approche a été présentée notamment en 1980 par Jon Bentley, Dorothea Haken, et James B. Saxe. Le théorème couvre un certain nombre de types de récurrences ; une extension à d'autres expressions est fournie par ce que l’on appelle la méthode d'Akra-Bazzi.