I'm reading CLRS and have came across the following question:
Which is asymptotically larger: $\lg \lg ^* n$ or $\lg^*\lg n$ ?
I understand there is a question which asks for exactly the same thing here.
However in the "proof" marked as answer, the writer concludes that
"Obviously $\lg^*m$ grows exponentially faster than $\lg(1 + \lg^*m)$"
but does not formally prove that $\lg^* m = \omega (\lg (1 + \lg^*m))$, i.e.
$$\forall C > 0 ~~~~ \exists n_0 > 0 ~~~~\forall n > n_0 ~~~~ \lg^*m \ge C\lg(1 + \lg^*m) \ge 0$$
so it is not so "obvious" after all.
As such I'd like to come up with a more rigorous proof and below is what I've tried:
My proof is as follows:
Note that by the definition of $\lg^*$, we have
$$lg^*n = \lg^*\lg n + 1$$ Taking $\lg$ of both sides, $$\lg \lg^* n = \lg(1 + \lg^*\lg n)$$ Since $\lg (1 + x) < x$ for all $x > 0$, $$\lg\lg^* n < \lg^*\lg n$$
So far so good, but the problem is that I have to show that
$$\forall C > 0 ~~~~\exists n_0 > 0 ~~~~\forall n\ge n_0 ~~~~\lg \lg^* n < C \lg^* \lg n$$
which will be an immediate result for all $C \ge 1$ as
$$\lg^* \lg n = 1\cdot \lg^* \lg n \le C\lg^* \lg n$$
but I am stuck as I am unable to think of anything for the interval $0 < C < 1$.
Observe that we have $$ \lg(n) = o(n - 1) $$ That is, for any $c > 0$, there exists a $N_0$ such that for any $n > N_0$, $\lg(n) < c\cdot (n - 1)$. It can be proved easily.
For any $c > 0$, let $M_0$ be a number such that $\lg^*(M_0) = N_0$. We have $$ \lg (\lg^*(m)) < c\cdot (\lg^*(m) - 1) = c\cdot \lg^*(\lg(m)) $$ for any $m > M_0$ since $\lg^*(m) > \lg^*(M_0) = N_0$.