# 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.

Labels:

• 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, at 11:02 PM

• something like..

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

By  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, 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  andy, at 11:45 AM

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

By  Anonymous, at 10:57 PM

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

By  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.