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

(unsw.edu.au)

17 points | by craigcitro 33 minutes ago

1 comments

flebron 13 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 8 minutes ago
  For those of us uninformed, what’s the difference between O and o?
  [-]
  - theokrueger 4 minutes ago
    Big O basically drops constants
    O(2n+1) = O(2n) = O(n)
    o(2n+1) > o(2n) > o(n)
  - boothby 4 minutes ago
    If f is O(g) and o(h) then
```
  Lim f/g -> C a constant
```
    And
```
  Lim f/h -> 0
```
    [-]
    - appplication 0 minutes ago
      Lmao! If someone is asking the difference between big and little o notation this is absolutely not the right way to clarify it.
      If you were joking then maybe you got me
  - Ygg2 1 minute ago
    Both are upper bounds. But small o is strictly smaller than upper bound. Big O is not greater than upper bound.
    https://stackoverflow.com/questions/1364444/difference-betwe...
- craigcitro 5 minutes ago
  ty, fixed. (ahh, copy paste.)