The number of digits needed to hold an output coefficient (and intermediate coefficients during the transform) increases with the number of input coefficients (

The number of digits needed to hold an output coefficient (and intermediate coefficients during the transform) increases with the number of input coefficients (because so many get added together). This forces the size of the ring to increase to accommodate the larger values, and pushes the runtime past O(n lg n).