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•32m ago
For those of us uninformed, what’s the difference between O and o?
theokrueger•28m ago
Big O basically drops constants
O(2n+1) = O(2n) = O(n)
o(2n+1) > o(2n) > o(n)
Both define upper boundary, but big O can read like "the function is generally proportional to ___" and little o can read like "the function is never more than _____"
bobmarleybiceps•14m ago
that's not the convention I know... (from CLRS algorithms book).
Big O is sort of like <=.
little o is sort of like <.
Roughly speaking, O(n log n) means "grows no faster than k(n log n) for some k", whereas o(n log n) means grows strictly more slowly* than k(n log n) for all* choices of k.
jdb1729•23m ago
> The new result does not directly imply new complexity bounds for polynomial multiplication over a fixed finite field, say multiplication in F2[x]. The state of the art for this problem is an algorithm that multiplies polynomials of degree n in time O(n log n 4^log*(n)) [HvdH19].
flebron•37m ago
onionisafruit•32m ago
theokrueger•28m ago
O(2n+1) = O(2n) = O(n)
o(2n+1) > o(2n) > o(n)
Both define upper boundary, but big O can read like "the function is generally proportional to ___" and little o can read like "the function is never more than _____"
bobmarleybiceps•14m ago
Big O is sort of like <=. little o is sort of like <.
https://dl.acm.org/doi/10.1145/1008328.1008329
npinsker•7m ago
O(n) is: "there exists a K such that, for sufficiently large n, K*n is always larger".
o(n) is: "for every K, for sufficiently large n, K*n is always larger". (So o(2n+1) and o(2n) and o(n) are the same thing.)
boothby•28m ago
appplication•24m ago
If you were joking then maybe you got me
boothby•5m ago
Ygg2•25m ago
https://stackoverflow.com/questions/1364444/difference-betwe...
ruined•21m ago
f(n) = o(g(n)) means as n increases, f(n)/g(n) must shrink
bobmarleybiceps•10m ago
craigcitro•29m ago
ComplexSystems•15m ago