Logarithme itéré

Le logarithme itéré de base b peut être défini par :

${\displaystyle \log _{b}^{*}n:={\begin{cases}0&{\mbox{si }}n\leq 1;\\1+\log _{b}^{*}(\log _{b}n)&{\mbox{si }}n>1.\end{cases}}}$

Sur les nombres réels positifs, le super-logarithmesuper-logarithme continu (l'inverse de la tétration) est essentiellement équivalente :

${\displaystyle \log _{e}^{*}n=\lceil \mathrm {slog} _{e}(n)\rceil }$

Le tableau suivant donne les valeurs du logarithme itéré (en base 2) :

${\displaystyle x}$	${\displaystyle \log _{2}^{*}x}$
${\displaystyle ]-\infty ;1]}$	0
${\displaystyle ]1,2]}$	1
${\displaystyle ]2,4]}$	2
${\displaystyle ]4,16]}$	3
${\displaystyle ]16,65536]}$	4
${\displaystyle ]65536,2^{65536}]}$	5

Cette fonction croît extrêmement lentement. Une fonction usuelle en informatique théorique qui croît encore plus lentement est la réciproque de la fonction d'Ackermann. Ces deux fonctions sont d'ailleurs liées, puisque le logarithme itéré est l'un des niveaux de la hiérarchie de la réciproque d'Ackermann[1].

• Cette fonction est utilisée pour l'analyse d'algorithmes, par exemple pour exprimer la complexité de l'algorithme de triangulation de Delaunay et en algorithmique distribuée, par exemple dans la borne inférieure de Linial pour la coloration de graphe[2].
• Dasgupta et al., dans leur livre d'algorithmique, présente une analyse de complexité amortie de la structure de données union-find en utilisant le logarithme itéré[3].
• Le logarithme itéré intervient dans la complexité de l'algorithme de Fürer.