Time Complexity

Question

log(log*n)  and  log*(logn)

Which function is in order of other??

Comments

log*(logn) is O(loglog(logn))             
log(log*n) is O(log(logn))

log*(logn) is O(log(log*n))

---

Found opposite answer on this site itself. can you see it and tell me which one is correct?

---

https://gateoverflow.in/62148/consider-following-functions-relations-between-function

---

put 2 in place of *

So, what is $log\left ( log^{*}n \right )$ will be $log\left ( log^{2}n \right )$

We can also write it as $log\left ( log n \right )^{2}$

 

Where as we can write $log^{*}\left ( log n \right )$

=$log^{2}\left ( log n \right )$

=$\left ( log\left ( log n \right ) \right )^{2}$

 

So, both function are different

Answer 1

f1 = log(log*n)  and  f2 = log*(logn)

log*n means in how may steps logn value will become 1, consider the following example, suppose n=$2^{128}$
log*$2^{128}$: 4 because 
log$2^{128}$ -> log$2^{7}$->Log2.80 -> log1.48 -> (approx 1) in 4 steps log*$2^{128}$ value has become 1, 

f1 = log(log*n) = log(4) =2
f2 = log*(logn) = log*128 = 3

Hence f1=O(f2), you consider even more larger value than $2^{128}$