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

1 comments

• flebron 9 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 4 minutes ago
    For those of us uninformed, what’s the difference between O and o?
    [-]
    • theokrueger 0 minutes ago
      Big O basically drops constants O(2n+1) = O(2n) = O(n) o(2n+1) > o(2n) > o(n)
  • craigcitro 1 minute ago
    ty, fixed. (ahh, copy paste.)