I am currently studying the complexity of matrix multiplication and Wikipedia's article says "The matrix multiplication algorithm that results of the definition requires, in the worst case, n³ multiplications of scalars and (n−1)n² additions for computing the product of two square n×n matrices. Its computational complexity is therefore O(n³), in a model of computation for which the scalar operations require a constant time (in practice, this is the case for floating point numbers, but not for integers)."

I'd like to know why integers' scalar operations does not require constant time.


The quote from Wikipedia doesn't say that scalar operations on integers don't take constant time; on the contrary, it says that the analysis of the matrix multiplication is based on the assumption that those scalar operations do take constant time. This assumption is stated not because it's false, but because it is true only in some contexts.

If you use a fixed-width integer type, such as 32-bit or 64-bit integers, then arithmetic operations such as + or * take asymptotically constant time simply because there are only finitely many different inputs, so whichever inputs they are slowest for is a constant bound on their running time.

On the other hand, if you use a language like Python where integers are not bounded by a fixed number of bits, then arithmetic operations are not constant time, and generally cannot be done in constant time on real hardware.

The algorithm we use to add numbers on paper requires adding the rightmost digits, maybe carrying a 1 to the next column left, adding the digits in that column and carrying, and so on in a loop. This algorithm is O(log n + log m) because the number of digits you need to add is logarithmic. The algorithm for adding integers in Python has a lot of special details regarding the data structure used to represent those integers, but the way it works is essentially the same; a loop over the digits of the number from right to left, in O(log n + log m) time.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy