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.
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: general math
7 Comments:
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 Anonymous, 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 Anonymous, 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 Coach Factory Online, at 2:43 AM
Post a Comment
<< Home