Many algorithms and data structures have iterated logarithms ($\log^\star n$) in their runtimes. This function is the discrete inverse of tetration, in that

$$\log_a^\star (a \uparrow \uparrow b) = b$$

There’s another inverse to tetration called the superroot, which satisfies this definition:

$$\sqrt[b]{a \uparrow \uparrow b}_S = a$$

I’ve never encountered this function in any context in algorithms or data structures. While the iterated logarithm naturally arises when, well, iterating logarithms, I don’t have any intuition for what the superroot does or where it would arise.

Does this function actually get used in the analysis of any algorithms or data structures?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.