wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> A recurrence formula with logloglog(n) solution.
        
(Message started by: Gennadiy Korol on Nov 8^th, 2007, 9:57am)

Title: A recurrence formula with logloglog(n) solution.
Post by Gennadiy Korol on Nov 8^th, 2007, 9:57am

Good time of the day everyone, I would like to share one of the riddles that I've came across recently.

We need to find the recurrence relation which solution is O( logloglog(n) ). O here denotes "Theta", the tight asymptotic bound.

For instance, the recurrence relation:

T(n) = T(n/2) + O(1) is of order O(log n).

That's pretty much all to it :)

Regards,
Gennadiy

Title: Re: A recurrence formula with logloglog(n) solutio
Post by Pietro K.C. on Nov 8^th, 2007, 9:25pm

Cute puzzle! The relation [hide]T(n) = T(\sqrt n) + O(1)[/hide] gives [hide]O(log log n)[/hide], and going one step further into the [hide]"reverse" Ackermann hierarchy[/hide] yields a full solution.

Title: Re: A recurrence formula with logloglog(n) solutio
Post by Hippo on Nov 29^th, 2007, 7:23am

Yes, for log⁽ⁱ⁾ n you gain equation f_i(n) = 2^(2^(2^...2^((log log log ... log n)-1)...)) where you use i times log and the same times 2^.

f_{i+1}(n) = 2^(f_i(log n))

for i=0 f_0(n)=n-1
for i=1 f_1(n)=2^(log n-1)=2^log (n/2) = n/2,
for i=2 f_2(n)=2^(2^(log log n - 1))=2^((log n)/2)=sqrt(n),
for i=3 2^(2^(2^(log log log n -1)))=2^sqrt(log n)

Title: Re: A recurrence formula with logloglog(n) solutio
Post by Gennadiy Korol on Dec 3^rd, 2007, 2:23pm

Yep!

Hippo: Thanks for providing the generalized solution, it gives some more insight into the problem. This is also one of the solutions I know for this riddle.

Pietro K.C.: My mathematic knowledge is on the undergraduate level, so I am not sure how to use Ackermann's inverse function in the particular case. I assume you are referring to the "towers of powers", similar to Hippo's suggestion?

There's also another solution to the original problem, very simple one, I would even call it cheating :) Its correctness follows immediately from the Master method.

Thanks for participating,
Gennadiy