Top
Best
New

Posted by baruchel 7 days ago

New proof dramatically compresses space needed for computation(www.scientificamerican.com)
186 points | 95 commentspage 2
baruchel 7 days ago|
Without paywall: https://www.removepaywall.com/search?url=https://www.scienti...
bluenose69 4 days ago||
Here's a quote from the SciAm article: "Technically, that equation was t/log(t), but for the numbers involved log(t) is typically negligibly small."

Huh?

asimpletune 4 days ago||
I think this means that while Log grows to infinity, it does that so slowly that it can often be treated as if it were a coefficient. Coefficients are ignored in big O notation, hence the negligibly small comment.
fwip 4 days ago|||
t/log(t) is 'closer to' t than it is to sqrt(t) as t heads toward infinity.

e.g:

    4/log2(4) = 4/2 = 2
    sqrt(4) = 2

    2^32/log2(2^32) = 2^32/32 = 2^27
    sqrt(2^32) = 2^16
tgv 4 days ago||
In case someone doesn't like the proof by example, here's a hint: sqrt(t) = t / sqrt(t).
burnt-resistor 4 days ago||
Maybe I'm missing context, but that sounds like O(n) or Ω(n).
snickerbockers 4 days ago||
>(Technically, that equation was t/log(t), but for the numbers involved log(t) is typically negligibly small.)

My dude, that is NOT how rational numbers work.

aaron695 4 days ago|
[dead]