Sorry to be pedantic but multiplication requires O(n ln(n)) not O(n^2) [1].<p>[1] <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Multiplication_algorithm#Fourier_transform_methods" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Multiplication_algorithm#Fouri...</a>