As n gets large, of the two functions log*(log n) and log(log* n) will will be faster?
Here, the log* function is the iterated logarithm, defined here:
I suspect these are the same, just written differently, but is there any difference between them?
Asked
Active
Viewed 4,211 times
6
templatetypedef
- 362,284
- 104
- 897
- 1,065
user97452
- 61
- 1
- 3
-
3if your asterisks are meant to indicate "logstar" aka n log n, you might want to re-write it that way, because SO has parsed them in a way I imagine you didn't intend – mfsiega Oct 04 '13 at 03:05
-
good call, no idea where I got that from – mfsiega Oct 04 '13 at 03:13
-
1If `log*` is shorthand for something a complete definition would be appreciated. – shuttle87 Oct 04 '13 at 03:19
1 Answers
16
log* n is the iterated logarithm, which for large n is defined as
log* n = 1 + log*(log n)
Therefore, log*(log n) = (log* n) - 1, since log* is the number of times you need to apply log to the value before it reaches some fixed constant (usually 1). Doing another log first just removes one step from the process.
Therefore, log(log* n) will be much smaller than log* (log n) = log* n - 1 since log x < x - 1 for any reasonably large x.
Another, more intuitive way to see this: the log* function is significantly better at compressing large numbers than the log function is. Therefore, if you wanted to take a large number and make it smaller, you'd get way more efficiency by computing log* n first to contract n as much as you can, then use log on that (log (log* n)) to pull down what's left.
Hope this helps!
templatetypedef
- 362,284
- 104
- 897
- 1,065