0

would you please explain me why does below equation hold? $$\log(\log^{*}(n)) = \Omega(\log^{*}(\log (n)))$$

This means that $\log^{*}(\log (n))$ in big $n$'s has a lower growth compared to $\log(\log^{*}(n))$

On the other hand, I have read in the book that $\text{logarithmic functions}$ have the same growth(theta of each other)

A Farmanbar
  • 115
  • What is logarithm with asterisk? – zkutch Jul 28 '20 at 05:03
  • @zkutch that is an university question that asked us. btw , it means that it can be repeated 0 to infinite – A Farmanbar Jul 28 '20 at 05:05
  • Ok. Then if it is only composition of logarithms what is difference between $\log^{}(\log n)$ and $\log(\log^{} n)$ ? – zkutch Jul 28 '20 at 05:08
  • @zkutch that's why i am asking for :) – A Farmanbar Jul 28 '20 at 05:09
  • From you definition - nothing, if under $*$ you understand same amount of compositions in one and second case. But as here maybe something more subtle, can you share your book, source from which you took definition? – zkutch Jul 28 '20 at 05:11
  • https://stackoverflow.com/questions/3797617/what-does-log-mean?noredirect=1&lq=1 this definition make more sense, are you agree with it? – zkutch Jul 28 '20 at 05:14
  • @zkutch sounds good materials there i have to read there and see if it gives answer. – A Farmanbar Jul 28 '20 at 05:15

1 Answers1

1

Suppose we take definition of $\log^{*}$ from here where definition says "The iterated logarithm is the number of times the logarithm has to be applied before the result becomes one or less".

So if we start from $n$ and apply $\log^{*}$, suppose, this gives $k$ steps of logarithm compositions until it becomes one or less. If for same $n$ we consider as start point $\log n$, then obviously we will have $k-1$ steps of logarithms composition from $\log^{*}$. Formally, for sufficiently big $n$, we have $$\log^{*}(\log n)=\log^{*}(n)-1 > \log(\log^{*}(n))$$

zkutch
  • 13,410