Théorème d'Akra-Bazzi

On considère l'équation de récurrence[1] :

${\displaystyle T(x)=g(x)+\sum _{i=1}^{k}a_{i}T(b_{i}x+h_{i}(x))\quad }$ pour ${\displaystyle x\geq x_{0},}$

où ${\displaystyle T:\mathbb {R} ^{+}\to \mathbb {R} ^{+}}$ est une fonction qui satisfait les conditions suivantes :

• La fonction est définie pour un nombre suffisant de valeurs initiales pour admettre une solution unique ;
• Les nombres ${\displaystyle a_{i}}$ et ${\displaystyle b_{i}}$ sont des constantes pour tous les indices ${\displaystyle i}$, et ${\displaystyle a_{i}>0}$ et ${\displaystyle 0<b_{i}<1}$ ;
• Pour la dérivée ${\displaystyle g'(x)}$ de ${\displaystyle g(x)}$, on a ${\displaystyle \left|g'(x)\right|=O\left(x^{c}\right)}$, pour une constante ${\displaystyle c}$ (${\displaystyle O}$ est le symbole de la notation de Landau) ;
• ${\displaystyle \left|h_{i}(x)\right|=O{\Bigl (}{\frac {x}{\log ^{2}x}}{\Bigr )}}$ pour tout i ;
• ${\displaystyle x_{0}}$ est une constante.

Alors ${\displaystyle T(x)}$ admet l'estimation suivante de son comportement asymptotique (${\displaystyle \Theta }$ le symbole de la notation de Landau) :

${\displaystyle T(x)=\Theta \left(x^{p}\left(1+\int _{1}^{x}{\frac {g(u)}{u^{p+1}}}\,\mathrm {d} u\right)\right)}$

où ${\displaystyle p\in \mathbb {R} ^{+}}$ est tel que ${\displaystyle \sum _{i=1}^{k}a_{i}b_{i}^{p}=1}$.

Les fonctions ${\displaystyle h_{i}(x)}$ représentent une petite perturbation de l’argument de T. Comme ${\displaystyle \lfloor b_{i}x\rfloor =b_{i}x+(\lfloor b_{i}x\rfloor -b_{i}x)}$ et comme ${\displaystyle \lfloor b_{i}x\rfloor -b_{i}x}$ est toujours compris entre 0 et 1, on peut utiliser ${\displaystyle h_{i}(x)}$ pour ignorer les différences avec les parties fractionnaires de l’argument. Par exemple, les fonctions ${\displaystyle T(n)=n+T\left({\frac {1}{2}}n\right)}$ et ${\displaystyle T(n)=n+T\left(\left\lfloor {\frac {1}{2}}n\right\rfloor \right)}$ ont, d'après le théorème d'Akra-Bazzi, le même comportement asymptotique[2].

Une variante de la condition sur la dérivée ${\displaystyle g'(x)}$ de ${\displaystyle g(x)}$ est la condition de croissance polynomiale de ${\displaystyle g(x)}$ qui s'énonce comme suit : il existe des constantes positives ${\displaystyle c_{1}}$ et ${\displaystyle c_{2}}$ telles que pour ${\displaystyle x\geq 1}$ on ait

${\displaystyle c_{1}g(x)\leq g(u)\leq c_{2}g(x)}$

pour tout réel ${\displaystyle u}$ dans la réunion des intervalles ${\displaystyle [b_{i}x,x]}$, pour ${\displaystyle 1\leq i\leq k}$.

Le théorème d'Akra-Bazzi couvre une très vaste classe d'équations récursives et généralise de manière substantielle les résultats connus précédemment pour déterminer le comportement asymptotique. Il est utilisé en informatique pour déterminer la complexité en temps d'algorithmes récursifs du type diviser pour régner. Les exemples suivants sont donnés dans les notes de Leighton[3] et repris dans un cours de Chowdhury[4]

Exemple 1

${\displaystyle T(x)=2T\left({\frac {x}{4}}\right)+3T\left({\frac {x}{6}}\right)+\Theta (x\log x)}$

On a ${\displaystyle p=1}$ et

${\displaystyle T(x)=\Theta \left(x\left(1+\int _{1}^{x}{\frac {u\log u}{u^{2}}}\,\mathrm {d} u\right)\right)=\Theta (x\log ^{2}x)}$

Exemple 2

${\displaystyle T(x)=2T\left({\frac {x}{2}}\right)+{\frac {8}{9}}T\left({\frac {3}{4}}x\right)+\Theta \left({\frac {x^{2}}{\log x}}\right)}$

On a ${\displaystyle p=2}$ et

${\displaystyle T(x)=\Theta \left(x^{2}\left(1+\int _{1}^{x}{\frac {u^{2}/\log u}{u^{3}}}\,\mathrm {d} u\right)\right)=\Theta \left({\frac {x^{2}}{\log \log x}}\right)}$

Exemple 3

${\displaystyle T(x)=T\left({\frac {x}{2}}\right)+\Theta (\log x)}$

On a ${\displaystyle p=0}$ et

${\displaystyle T(x)=\Theta \left(1+\int _{1}^{x}{\frac {\log u}{u}}\,\mathrm {d} u\right)=\Theta (\log ^{2}x)}$

Exemple 4

${\displaystyle T(x)={\frac {1}{2}}T\left({\frac {x}{2}}\right)+\Theta \left({\frac {1}{x}}\right)}$

On a ${\displaystyle p=-1}$ et

${\displaystyle T(x)=\Theta \left({\frac {1}{x}}\left(1+\int _{1}^{x}{\frac {1}{u}}\,\mathrm {d} u\right)\right)=\Theta \left({\frac {\log x}{x}}\right)}$

Article original

• Mohamad Akra et Louay Bazzi, « On the solution of linear recurrence equations », Computational Optimization and Applications, vol. 10, n^o 2,‎ 1998, p. 195-210 (MR 99c:68115, présentation en ligne) — Springer montre les deux premières pages.

Exposés pédagogiques

• Tom Leighton, « Notes on Better Master Theorems for Divide-and-Conquer Recurrences », 6.046: Introduction to Algorithms - Spring 2004 : Handout, Massachusetts Institute of Technology, 1996.
• Kurt Mehlhorn et P. Saunders, « A Master Theorem for Recurrences », Data Structures and Algorithms (complément), Max Planck Institut, 2008.
• Rezaul A. Chowdhury, « Divide-and-Conquer Algorithms: Akra-Bazzi Recurrences », CSE 548 : Analysis of Algorithms : Lectures 7 & 8 Fall 2012, Department of Computer Science, SUNY Stony Brook, 2012.