I know the iterative logarithm can only produce 1 of 6 numbers. However, I don't really understand how to solve. Can someone please explain how to solve $\log^*n$ where $n$ is any number, lets say like 100. Would there be any difference for $\lg^*n$?
Asked
Active
Viewed 199 times
1
3 Answers
2
Suppose we'd like to solve $\log^*100$ with a base-10 logarithm. $\log100=2$, which is greater than 1, but $\log\log100$ is less than 1. Thus $\log^*100=2$.
For $\lg^*100$ (base 2) we have $$\lg100=6.644$$ $$\lg\lg100=2.732$$ $$\lg\lg\lg100=1.450$$ $$\lg\lg\lg\lg100=0.536$$ so $\lg^*100=4$.
These functions sometimes come up in analysis of algorithms, and they grow very slowly. While they can theoretically take on any value, for all practical values of $x$ even $\lg^*x$ is always five or less.
Parcly Taxel
- 103,344
-
oooh, so it's basically the number of iterations until the answer is less than 1? – Adjit Sep 18 '17 at 18:52
-
1
There I a huge difference between $\log_{10} n$ and $\log_2 n$.Let the first value be $x$ and the second be $y$.Then $n=2^x$ and $n=10^y$.That's why The value of $x$ and $y$ after different. To solve it you have to write $n$ as a power of $10$. Examples:1) $\log_{10} 100=\log_{10} 10^2=2$
2)$\log_{10} 200=\log_{10} 100 + \log_{10} 2=2+\log2$
user3658307
- 10,433
Sufaid Saleel
- 3,789
-
-
@Adjit It is done in the question.And if you need more explanation then tell me.And read the theorems of logarithm properly – Sufaid Saleel Sep 18 '17 at 03:44
1
In fact, $Log^{*}(n)$ is a recursive function.
$$Log^{*}(n) = \begin{cases}Log^{*}(log(n))+1 \qquad if\text{ } log(n)\geq 1\\ 0\qquad\qquad\qquad\qquad\text{ }\text{ } if\text{ }log(n)< 1\end{cases}$$
Hasan Heydari
- 1,187
- 1
- 8
- 22
log= base 10;lg= base 2 – Adjit Sep 18 '17 at 03:33