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

1 comments

• flebron 11 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 6 minutes ago
    For those of us uninformed, what’s the difference between O and o?
    [-]
    • boothby 1 minute ago
      If f is O(g) and o(h) then

        Lim f/g -> C a constant
      

      And

        Lim f/h -> 0
    • theokrueger 1 minute ago
      Big O basically drops constants

      O(2n+1) = O(2n) = O(n)

      o(2n+1) > o(2n) > o(n)
  • craigcitro 2 minutes ago
    ty, fixed. (ahh, copy paste.)