FFT for multiplication and has a well understood complexity of nlogn w.r.t number of digits. “Regular” multiplication could mean n^2 for standard paper arithme

FFT for multiplication and has a well understood complexity of nlogn w.r.t number of digits. “Regular” multiplication could mean n^2 for standard paper arithmetic, n^1.6 for karatsuba, and a few other n^y algorithms with y>1 However as usual in this analysis we have dropped constant factors and the constant factors for FFT are high so you have to be multiplying numbers with at least hundreds of digits if not thousands. Note that the base of the digits isn’t relevant for analytical performance, as it’s a constant factor change