log*
is the number of times you needed to take log
in order to nullify the value.
It is NOT infinite time log. Taking infinite time logs will just result in negative number at the end, and then it will be undefined, which does not make sense here.
For example:
log*(2^1024) = 1 + log*(log(2^1024)) = 1 + log*(1024) = 1 + 1 + log*(log(1024) = 2 + log*(10)
= 2 + 1 + log*(log(10)) = 3 + log*(3) = 3 + 1 + log*(log(3)) = 4 + log*(2)
= 4 + 1 + log*(log(2)) = 5 + log*(1) = 5
now, on the other hand
log(log*(2^1024)) = log(5) = 3
(In the above, all log are base 2, and I always took the ceil value of non integers, these assumption do not change the principle explained here)
UPDATE (response to update in question):
You can't just make one extra log, because you need to introduce an extra improvement to your algorithm that is making it happen.
Your improvement from O(m log*(n))
to O(m log(log*(n))
did not came out of nowhere, it came out from some improvement to the algorithm. If you can find another improvement with similar behavior, you might be able to get O(m log(log(log*(n))))
.