Author |
Topic: A recurrence formula with logloglog(n) solution. (Read 3907 times) |
|
Gennadiy Korol
Newbie
Gender: 
Posts: 2
|
 |
A recurrence formula with logloglog(n) solution.
« on: Nov 8th, 2007, 9:57am » |
 Quote  Modify
|
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
|
|
 IP Logged |
|
|
|
Pietro K.C.
Full Member
 
Gender:
Posts: 213
|
|
Re: A recurrence formula with logloglog(n) solutio
« Reply #1 on: Nov 8th, 2007, 9:25pm » |
Quote Modify
|
Cute puzzle! The relation T(n) = T(\sqrt n) + O(1) gives O(log log n), and going one step further into the "reverse" Ackermann hierarchy yields a full solution.
|
| « Last Edit: Nov 8th, 2007, 9:25pm by Pietro K.C. » |
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: A recurrence formula with logloglog(n) solutio
« Reply #2 on: Nov 29th, 2007, 7:23am » |
Quote Modify
|
Yes, for log(i) 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)
|
| « Last Edit: Nov 29th, 2007, 7:23am by Hippo » |
IP Logged |
|
|
|
Gennadiy Korol
Newbie
Gender:
Posts: 2
|
|
Re: A recurrence formula with logloglog(n) solutio
« Reply #3 on: Dec 3rd, 2007, 2:23pm » |
Quote Modify
|
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
|
| « Last Edit: Dec 3rd, 2007, 2:26pm by Gennadiy Korol » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print