Growth of Functions - What is "Log Star" (O(log*n))?

[gnome]

I'm not sure this belongs here, but I don't know where else to post it:

On a handout from my Analysis of Algorithms class there's a "Hierarchy of Functions" chart which includes familiar orders such as
log n, linear, n log n, quadratic, cubic, exponential, etc.

There is one that I've never seen before, I don't know what it means & I can't find anything written about it.

He calls it "log star", also written as log*n.
It's the second-lowest listed in the hierarchy, between "constant" and "log log"; that is, an algorithm that is O(log*n) is a very good one, better than O(log-log n).

Any ideas what it means?

 

[master_coda]

As far as I know:

\log^*n=\min\lbrace x\in\mathbb{N}\vert \log_2^xn<2\rbrace

In other words, the log-star of a number is the minimum number of times you would have to apply the base-2 log to a number to get a results that is less than 2. An algorithm which is O(\log^*n) is considered to have an almost-constant running time. While the algorithm is not strictly speaking constant-time, you could increase the amount of input by a factor of 10^{15} and only increase the running time by a factor of 5.

 

[gnome]

Who thinks of these things?

Sorry, I still don't get it. What's inf{...

Can you give me an example of what would be log*n if n is say, 10000?

 

[master_coda]

Originally posted by gnome
Who thinks of these things?

Sorry, I still don't get it. What's inf{...

Can you give me an example of what would be log*n if n is say, 10000?

I replaced inf with min when I realized using it here was both unnecessary and confusing. There's a slightly stronger definition where you need to use inf.

log*10000 = 3 because log(log(log 10000)) < 2 and log(log 10000) >= 2. Note that this is using log base 2.

To find the log-star of a number, just count the number of times you have to apply log (base 2) to it to get a result less than 2.

 

[gnome]

Thank you.

Now, is there an easier way to get that on a calculator than doing this:

ln (ln (ln 10000/ln2) /ln2) /ln2 = 1.899...

?

 

[master_coda]

Originally posted by gnome
Thank you.

Now, is there an easier way to get that on a calculator than doing this:

ln (ln (ln 10000/ln2) /ln2) /ln2 = 1.899...

?

I can't think of one. But:

log*2 = 1
log*4 = 2
log*16 = 3
log*65536 = 4

Unless you're working with numbers >= 2^65536 then you should be able to use those values to figure out the values in your head (they'll always be between 0 and 5).

But someone else here may be more clever than me. And there is also another version of this function that gives real numbers instead of integers (for example, log*15 would not be 2 but rather a number between 2 and 3). However I definitely don't know how to calculate that version.

If you can wait 3 months, I can find out in my Algorithms class next term.