I thought about this question while looking at a textbook where it wanted me to compare the time complexity of $\lg^*(n)$ and $\lg^*(\lg(n))$

Now it is well known that $\lg^*$ is a tremendously slow growing function, so what is inside of $\lg^*$ shouldn't contribute to its complexity.

But is it true in general that any $f(g)$ is $O$-equivalent to $f(h)$ where f is a non constant function?

  • 3
    $\begingroup$ Where function $h$ comes from? Your question is not clear. $\endgroup$ – jonaprieto Dec 15 '14 at 4:49
  • 1
    $\begingroup$ Of course what's inside the $\log^*$ can contribute to the complexity. Define $t(0) = 1$, $t(n+1)=2^{t(n)}$. Then $\log^*(t(n)) = \Theta(n)$, for example. $\endgroup$ – David Richerby Dec 15 '14 at 9:37

No, $f \circ g$ and $f \circ h$ (to use the standard mathematical notation) do not in general have the same complexity. For example, take $g(x) = 1$ (constant function) and $h(x) = x$ (identity function). Then $(f \circ g)(x) = f(1)$ and $(f \circ h)(x) = f(x)$; these functions only have the same complexity if $f = \Theta(1)$ (i.e. $f$ is asymptotically constant). This shows that the only functions $f$ for which all functions of the form $f \circ g$ have the same complexity are the ones that are asymptotically constant.

With the example $f = \lg^*$, growth is very slow, so a lot of functions “collapse” when you plug them into $\lg^*$. Nonetheless it is easy to cancel this collapse: define the function $e(y) = \min\{x \mid \lg^*(x) \ge y\}$. This is essentially an inverse function for $\lg^*$ (growing by $1$ at increasingly long intervals). With this you can easily construct functions that grow at any rate you like: $f(e(x)) \approx x$, $f(e(x^2)) \approx x^2$, etc.

(N.B. In my mathematical statements, I assume functions from $\mathbb{N}$ to $(0,\infty)$.)


No. First of all, You got the function $f(x) = \lg(x)$. And we know that this function is monotonically increasing. So, In the domain of this function always is true with $\epsilon \in (0, +\infty]$ $$ \lg(x) < \lg(x+\epsilon)$$ Cause of that, if you apply in a inequality this function $f$ to each member. This inequality conserves the form. In your example, $x \in [1, +\infty]$ $$ \begin{align} \lg(x) &\leq x \\ \lg(\lg(x)) &\leq \lg(x) \end{align} $$ For that, and by definition of landau notation. $\lg(\lg(x)) \in O(\lg(x))$. Remember the definition, specifically the quantifiers (i.e $\exists,\ \forall $). Last but not least. If $g\in O(h)$ and $f$ is monotocally increasing like this case, $(f\circ g)(x)\in O(f\circ h)$.

Now, you are using the a iterative logarithm $\lg^*$ that is a function define as next:

$$ \lg^* n := \begin{cases} 0 & \mbox{if } n \le 1; \\ 1 + \lg^*(\lg n) & \mbox{if } n > 1 \end{cases} $$

So, this function counts likely the number of times that you need to apply the logarithm function to the argument to achieve an outcome less or equal to 1.

For that, considering a value greater than 1, you have to need more iterations of logarithm with $n$ parameter than a less value, $\lg(n)$. Actually,

$$ \lg^*(\lg n) \leq 1+ \lg^*(\lg n) \leq \lg^* (n) $$

  • $\begingroup$ Yes, I agree. But what do you think would happen if I exchange $lg$ with $lg^*$. Note here $lg^*$ is truly painfully slow growing function, would there still be a difference? $\endgroup$ – Carlos - the Mongoose - Danger Dec 15 '14 at 5:03
  • $\begingroup$ Not difference. But just, to clarify, what mean your notation of $\lg^*$? $\endgroup$ – jonaprieto Dec 15 '14 at 5:10
  • $\begingroup$ en.wikipedia.org/wiki/Iterated_logarithm $lg^*$ is log-star or iterated logarithm. Note $lg^*(n) = 5$ if n is the number of atoms in the entire universe $\endgroup$ – Carlos - the Mongoose - Danger Dec 15 '14 at 5:16
  • $\begingroup$ Look, the $\lg^*$ is like a function that counts the number of times you need to apply the log to got 1 or less value so with function $f(n) = n$ will take more steps than to actually less value $\log(n)$. I update the answer. $\endgroup$ – jonaprieto Dec 15 '14 at 5:40

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.