Difference between O(m log(log* n)) and O(m log* n) with iterative log function

Question

When I was taking algorithms class talking about minimum spanning trees, my professor introduced a performance enhancement from O(m log* n) to O(m log(log* n)) by Fredman and Tarjan.

I get really confused by this taking log of iterative log. It seems that log* n is essentially taking infinitely many logs, so to me this is like comparing infinity with infinity+1.

Anyone can give a kind explanation? Analogy is also welcome.

---

Update:

Thanks for the quick answers to correct me!

Further question:

It seems that this complexity comes from iterative algorithms.

If we can take one more log of the iterative log, why can't we take one more to get O(m log(log(log* n))) to further reduce the complexity?

---

Thanks amit!

I need to improve on the concepts haha!

Answer 1

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)))).

Answer 2

The value of log* n is the number of log that are require for reducing n to 1. For base 2:
log* 16 = 1 + log* 4 = 2+ log* 2 = 3. While log(log* 16) is log 3.

See this definition : http://en.wikipedia.org/wiki/Iterated_logarithm