What does "log*" mean?

It's called iterated logarithm function. It is a very slowly growing function. For example:

• lg*(2) = 1
• lg*(4) = 2
• lg*(16) = 3
• lg*(65536) = 4
• lg*(2^65536) = 5 /note that (2^65536) is much larger than the number of atoms in the observable universe/

Or in the case of Big O it could pretty much be considered as constant time.

It's iterated logarithm. See here for a description of lots of different time complexities, and here for more details on the iterated logarithm itself.

The iterated logarithm is the number of times the logarithm has to be applied before the result becomes one or less.