I think you&#x27;re right, but it depends on what&#x27;s your computational model. In word-RAM you usually assume that log n &lt; w where w is the machine word, and you can do arithmetical operations on words in O(1), so if your coefficients fit in w bits the complexity is O(n log n). You could say it&#x27;s a trick but it&#x27;s a convenient trick, since on a real-world machines w is much larger than you need (64). I don&#x27;t know if you can make the same argument about floating point computations.