Register to reply 
Growth of functions 
Share this thread: 
#1
Feb704, 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 secondlowest 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(loglog n). Any ideas what it means? 


#2
Feb704, 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 logstar of a number is the minimum number of times you would have to apply the base2 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 almostconstant running time. While the algorithm is not strictly speaking constanttime, 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. 


#3
Feb704, 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? 


#4
Feb704, 05:58 PM

P: 678

Growth of functions
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 logstar 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. 


#5
Feb704, 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... ? 


#6
Feb704, 07:04 PM

P: 678

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 