4 ms·

Here you go: Õ (read soft-O) See: http://en.wikipedia.org/wiki/Big_O_notation#Extensions_to_the_Bachmann.E2.80.93Landau_notations http://en.wikipedia.org/wiki/

by rawnlq 12y ago

Here you go: Õ (read soft-O) See: http://en.wikipedia.org/wiki/Big_O_notation#Extensions_to_the_Bachmann.E2.80.93Landau_notations http://en.wikipedia.org/wiki/Big_O_notation#Extensions_to_th... (basically means ignore multiplicative log factors) Also, to play devil's advocate, why not say all log factors are effectively constant? Note that 5 * log_32(x) = log_2(x) or to use your example, log_2(2^48) <= 50.

lomnakkus 12y ago
Interesting. I was not aware of that notation, thank you. Re: "all log factors": Agreed, as long as the base of the logarithm is high enough, obviously :). I'm well aware that the base doesn't matter mathematically, but in practice it actually does. Especially since 32 is the number of bits in a CPU word, and thus neatly fits into cache lines, is easily manipulable by CPU instructions, etc. etc. (See Bagwell's papers for details.)