The recently proposed O(n log n) integer multiplication algorithm [pdf]

1 comments

• flebron 6 minutes ago
  Note 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.
  [-]
  • onionisafruit 1 minute ago
    For those of us uninformed, what’s the difference between O and o?