反復対数
Richard ColeとUzi Vishkinによるグラフの3彩色問題の分散アルゴリズム - O ( log ∗  n ) {\displaystyle O(\log ^{*}n)} 回の同期通信ステップ。
反復対数の成長は非常に遅く、対数関数よりもはるかに遅い。実装されている実際のアルゴリズムの実行時間を数えるのに十分な n {\displaystyle n} のすべての値(すなわち n ≤ 2 65536 ∼ 10 19660 {\displaystyle n\leq 2^{65536}\sim 10^{19660}} 、この最大値は観測可能な宇宙内の原子数 10 80 {\displaystyle 10^{80}} を優に超える)に対して、底 2 {\displaystyle 2} の反復対数の値はたったの 5 {\displaystyle 5} 以下である。
より高い底の反復対数は、より小さい値を返す。計算の複雑さの分野で使われるものでいえば、逆アッカーマン関数だけである。