David Harvey and Joris van der Hoeven proved at this year that the product of two integers whose bit length is $O(n)$ can be computed in $O(n\log n)$.
I've heard that the optimal complexity of multiplication has been believed to be $O(n \log n)$ 30 years simply because the FFT can be computed in $O(n \log n)$.
Now I have question.
Considering two integer $A$ and $B$ such that
$$A=\sum_{i=0}^{n-1}a_i 10^i \ (0\leq a_i <10),$$ $$B=\sum_{i=0}^{n-1}b_i 10^i \ (0\leq b_i <10).$$
We want to calculate the product of $A$ and $B$. By FFT, product of two polynomials,$A'(x)=\sum_{i=0}^{n-1}a_i x^i$ and $B'(x)=\sum_{i=0}^{n-1}b_i x^i$ can be computed in $O(n\log n)$.
Then, just calculating the increasing of digit from the lower digit.
What is the time complexity of this algorithm? Apparently, the upper bound of time complexity is $O(n^2)$ when $n$ digit increasing happens at every digit. However, I cannot construct such case.