Timeline for Recurrence T(N)=T(N/LOGN)+1 [closed]
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 11, 2012 at 23:03 | history | closed |
Will Jagy Felipe Voloch Chandan Singh Dalawat Andy Putman Suvrit |
too localized | |
| Mar 11, 2012 at 14:32 | answer | added | Kevin O'Bryant | timeline score: 1 | |
| Mar 11, 2012 at 14:29 | answer | added | Brendan McKay | timeline score: 2 | |
| Mar 11, 2012 at 13:10 | answer | added | iensen | timeline score: 1 | |
| Mar 10, 2012 at 23:33 | answer | added | David Harris | timeline score: 0 | |
| Mar 10, 2012 at 22:34 | comment | added | iensen | >It will be bounded from below by logn/loglogn Yes,i have got this by replacing LOGN with LOG N_F,where N_F is N which was an argument of the first call. Do you have any ideas for the upper bound? | |
| Mar 10, 2012 at 22:30 | comment | added | David Harris | It will be bounded from below by $\log n/\log \log n$. | |
| Mar 10, 2012 at 22:29 | comment | added | iensen | This equation (like most questions on math.stackexchange.com,but i didn't find exactly this one) originate from Cormen's book about algorithms. It is not stated clearly anywhere but it can be composed on the base of one of the book's chapters. | |
| Mar 10, 2012 at 22:26 | comment | added | iensen | I believe the approximation log(n/logn) is not correct. T(1000 000)= 7,T(1000 000 000 )=9...,it grows much slower. I wonder if there is a method for solving such equations | |
| Mar 10, 2012 at 22:24 | comment | added | Yemon Choi | This looks vaguely (but probably not exactly) like questions asked on math.stackexchange.com - where does this recurrence relation originate? | |
| Mar 10, 2012 at 22:18 | comment | added | Gerhard Paseman | T(n) will be bounded above by log(n) with the log base being 2. It is likely to be approximated for large n by something like log(n/log(n)), but I have not verified this. Gerhard "Ask Me About System Design" Paseman, 2012.03.10 | |
| Mar 10, 2012 at 22:15 | history | edited | iensen | CC BY-SA 3.0 |
added 55 characters in body; added 1 characters in body
|
| Mar 10, 2012 at 22:14 | comment | added | iensen | Oh sorry,the log is "binary" log with base 2. | |
| Mar 10, 2012 at 22:11 | comment | added | Woett | Well, there is no such function. Check N = e, for example. | |
| Mar 10, 2012 at 22:00 | history | asked | iensen | CC BY-SA 3.0 |