Some algorithms have a running time which involves $\log^* n$, the number of iterations of $\log$ before the result is at most $1$. This is essentially the inverse of tetration base $e$. For example, the Fredman-Tarjan algorithm for finding a minimal weight spanning tree has run time $E ~\log^* V$, and the randomized algorithm by Clarkson et al. for triangulating a simple polygon with $n$ vertices has expected running time $n ~\log^* n$. (In both cases, there are asymptotically faster algorithms by Bernard Chazelle.)
|
1 | [made Community Wiki] | ||
|
|
||||
