alt Hacker NewsNote in this case the title says "O(n log n)", but the important part is this is "o(n log n)", not just "O(n log n)'. The former is a strict subset of the latter. We already knew how to multiply two n-bit integers in O(n log n) time, via the FFT.
Replies
onionisafruit • today at 2:55 AM
For those of us uninformed, what’s the difference between O and o?
➕ show 5 replies
craigcitro • today at 2:58 AM
ty, fixed. (ahh, copy paste.)
Roughly speaking, O(n log n) means "grows no faster than k(n log n) for some k", whereas o(n log n) means grows strictly more slowly* than k(n log n) for all* choices of k.