Register to reply

Growth of functions

by gnome
Tags: functions, growth
Share this thread:
gnome
#1
Feb7-04, 03:37 PM
P: 1,046
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?
Phys.Org News Partner Science news on Phys.org
Fungus deadly to AIDS patients found to grow on trees
Canola genome sequence reveals evolutionary 'love triangle'
Scientists uncover clues to role of magnetism in iron-based superconductors
master_coda
#2
Feb7-04, 05:39 PM
P: 678
As far as I know:

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

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 [itex]O(\log^*n)[/itex] 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 [itex]10^{15}[/itex] and only increase the running time by a factor of 5.
gnome
#3
Feb7-04, 05:50 PM
P: 1,046
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
#4
Feb7-04, 05:58 PM
P: 678
Growth of functions

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
#5
Feb7-04, 06:35 PM
P: 1,046
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
#6
Feb7-04, 07:04 PM
P: 678
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.


Register to reply

Related Discussions
Sum/integral/zeta functions/ Gamma functions Calculus 3
Functions and Realtions : Operation on Functions [Please Answer NOW. I need it today] Precalculus Mathematics Homework 2
Moment Generating Functions and Probability Density Functions Set Theory, Logic, Probability, Statistics 4
Trigonometric Functions..simplify sin squared functions Precalculus Mathematics Homework 2
Growth and Decay Functions? Introductory Physics Homework 10