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?
ReplyDeleteh(n) still seems to be quasipolynomial..
g(n) = f(n) * log n factors
h(n) = f(n) * log n factors * log log n factors ...
something like..
ReplyDeleten^((lg n)^((lglg n)^(c-1)-1))
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.
ReplyDeletearavind srinivasan
thanks, friends!
ReplyDeleteanon 1, g(n) is not equal to a polynomial times lower-order terms. Nor is h(n) equal to a quasipoly times LOTs.
I don't know my > from my ( or even my [, but I liked the Steely Dan reference!
ReplyDeleteThanks! That reminds me of something I should post about...
ReplyDeleteHey! 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.
ReplyDelete