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$.

  • $\begingroup$ Okay. noted. But how could we get to define a recurrence based on it ? BTW, Thank you for the clear and concise explaination. $\endgroup$ – Sachin Bahukhandi Jun 14 '20 at 10:35
  • $\begingroup$ 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? $\endgroup$ – Steven Jun 14 '20 at 10:36
  • $\begingroup$ Reurrence like stated here: en.wikipedia.org/wiki/Iterated_logarithm $\endgroup$ – Sachin Bahukhandi Jun 14 '20 at 10:37
  • $\begingroup$ So you want a recursive definition of $\log^* n$? There is one right in the page you linked. $\endgroup$ – Steven Jun 14 '20 at 10:38
  • $\begingroup$ Yeah. But how could we get to it. $\endgroup$ – Sachin Bahukhandi Jun 14 '20 at 10:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.