> 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].
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 10 minutes ago [-]
For those of us uninformed, what’s the difference between O and o?
theokrueger 6 minutes 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 _____"
boothby 6 minutes ago [-]
If f is O(g) and o(h) then
Lim f/g -> C a constant
And
Lim f/h -> 0
appplication 2 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 3 minutes ago [-]
Both are upper bounds. But small o is strictly smaller than upper bound. Big O is not greater than upper bound.
@platypii and I obtained a Lean proof of the same improvement for DFT over prime-order finite fields (yielding polynomial multiplication via the convolution theorem): https://github.com/platypii/integer-mult-bounds-lean/blob/ma...
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 _____"
If you were joking then maybe you got me
https://stackoverflow.com/questions/1364444/difference-betwe...