# Computation of iterated logarithm function

I recently came across the iterated algorithm function denoted as $$\lg^* n$$.

But I am having a hard time understanding this statement:

$$\lg^* n = \min \{i \ge 0: \lg^{(i)} n ≤ 1\}$$

I could not understand what $$\min$$ set is used to signify. Also, could someone please provide an example of how this works. I also came across examples like:

$$\lg^* 4= 2$$

But could not understand the computation, specifically how did they take up the values of i?

Thank you.

$$\lg^* n$$ is just the minimum number of times you need to apply the $$\lg$$ function to $$n$$ in order to obtain a number that is smaller than or equal to $$1$$.

For example, assuming that you are working with base-2 logarithms and that $$n=65536$$ you have the following:

• $$\lg^{(0)} 65536 = 65536$$,
• $$\lg^{(1)} 65536 = \lg 65536 = 16$$,
• $$\lg^{(2)} 65536 = \lg 16 = 4$$,
• $$\lg^{(3)} 65536 = \lg 4 = 2$$,
• $$\lg^{(4)} 65536 = \lg 2 = 1$$.

As you can see $$4$$ is the smallest integer value of $$i \ge 0$$ for which $$\lg^{(i)} 65536 \le 1$$. Therefore $$\lg^* 65536 = 4$$.

• Okay. noted. But how could we get to define a recurrence based on it ? BTW, Thank you for the clear and concise explaination. – Sachin Bahukhandi Jun 14 '20 at 10:35
• What do you mean by "define a recurrence based on it"? Do you want a recurrence relation that has $\Theta( \log^* n )$ as a solution? – Steven Jun 14 '20 at 10:36
• Reurrence like stated here: en.wikipedia.org/wiki/Iterated_logarithm – Sachin Bahukhandi Jun 14 '20 at 10:37
• So you want a recursive definition of $\log^* n$? There is one right in the page you linked. – Steven Jun 14 '20 at 10:38
• Yeah. But how could we get to it. – Sachin Bahukhandi Jun 14 '20 at 10:41