Andy's Math/CS page

Friday, April 04, 2008

Some babies grow in a peculiar way

Today I bumped into an order of growth I hadn't seen before, and thought I'd share it for a modest bit of mental aerobics.

Readers may well have seen functions of form

f(n) = (log n)^c,

known as 'polylogarithmic'. These are important in, e.g., query complexity, where we like the number of queries to be much smaller than the input size n when possible. Also emerging from such studies are the 'quasipolynomial' functions, of form

g(n) = 2^{(log n)^c}.

As a warmup--how fast do these things grow?

OK, now the main course tonight is the following:

h(n) = 2^{2^{(log log n)^c}}.

What do you make of these? And what questions need answering before we understand such a growth rate 'well enough'? I'm unsure and would love to hear your thoughts.



  • Shouldnt that start from f(n) = n^c?

    h(n) still seems to be quasipolynomial..

    g(n) = f(n) * log n factors
    h(n) = f(n) * log n factors * log log n factors ...

    By Anonymous Anonymous, at 11:02 PM  

  • something like..

    n^((lg n)^((lglg n)^(c-1)-1))

    By Anonymous Anonymous, at 12:35 AM  

  • Andy, check out this paper of David Zuckerman, to see how NP-hard problems have a version that's hard to approximate even up to any constant number of iterations of the types of functions you describe.

    aravind srinivasan

    By Anonymous Anonymous, at 10:16 AM  

  • thanks, friends!

    anon 1, g(n) is not equal to a polynomial times lower-order terms. Nor is h(n) equal to a quasipoly times LOTs.

    By Anonymous andy, at 11:45 AM  

  • I don't know my > from my ( or even my [, but I liked the Steely Dan reference!

    By Anonymous Anonymous, at 10:57 PM  

  • Thanks! That reminds me of something I should post about...

    By Anonymous Andy, at 11:25 PM  

  • Hey! Coach Factory Online simply wanted to say your website is one of the nicely laid out, most inspirational I have come across in quite a while.

    By Anonymous Coach Factory Online, at 2:43 AM  

Post a Comment

<< Home