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

(unsw.edu.au)

17 points | by craigcitro 32 minutes ago

1 comments

flebron 12 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 7 minutes ago
  For those of us uninformed, what’s the difference between O and o?
  [-]
  - theokrueger 3 minutes ago
    Big O basically drops constants
    O(2n+1) = O(2n) = O(n)
    o(2n+1) > o(2n) > o(n)
  - boothby 3 minutes ago
    If f is O(g) and o(h) then
```
  Lim f/g -> C a constant
```
    And
```
  Lim f/h -> 0
```
  - Ygg2 0 minutes 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 4 minutes ago
  ty, fixed. (ahh, copy paste.)