Question

consider the following functions f(n)=log*(log n) , g(n)=log(log* n) relations between these 2 function. please help

Comments

log*n is the no.of times we can take log repeatedly until we get 1.

This is can be done in constant amount of time.

F=Log*(logn) = klogn where k is constant.

G= Log(log*n) = logk  where k is constant

So G is O(F)

Answer 1

$f(n)=\log^*(\log n)$

$= \log^* n - 1$ from definition of $\log^*$ which is to take $\log$ recursively until we get 1.

$g(n)=\log(\log^* n)$ is clearly a smaller growing function than $f$ as it is growing in $\log$ terms to $f$. So,

$$g(n) = O(f(n))$$