What Is the Time Complexity of a Modulo Operation?
At a glance
- 1. Choose a number model
Decide whether the inputs fit in fixed-width machine words or are arbitrary-precision integers.
- 2. Measure input size
For large integers, use the number of bits in the operands, not their numeric values.
- 3. Apply the right bound
A word-sized remainder is usually constant time; big-integer remainder takes time that grows with operand length.
- 4. Check the convention
For negative operands, languages may define remainder differently, but this does not change the asymptotic cost.
The time complexity of a % b depends on how the integers are represented and what counts as one operation. Assume throughout that the divisor is nonzero; modulo by zero is not defined as an integer remainder and is typically an error or undefined behavior in programming languages. For ordinary fixed-width integers, the operation is usually described as constant time. For integers that can grow to hundreds or thousands of bits, the operation takes longer as the input grows.
The reason is that computing a remainder is closely related to integer division: division gives a quotient, and the remainder is determined by the dividend, quotient, and divisor. So the right complexity depends on the cost of division in the computational model you are using.
Fixed-width machine integers
In the usual word-RAM model, a machine word holds a fixed number of bits, such as 32 or 64. If both operands fit in one word, arithmetic operations on them are commonly assigned unit cost. Under that convention, a % b is O(1).
This is an asymptotic model, not a claim that remainder takes exactly the same number of processor cycles as addition. A processor may have a hardware division instruction with a particular latency, or a compiler may implement remainder using several instructions. With a fixed word size, those are bounded costs as the input size grows, so they count as constant time in the model.
If an analysis treats the word size itself as a variable, the answer can differ. For example, an operation on a word of w bits may take a cost that depends on w. State the model when that distinction matters.
Arbitrary-precision integers
Libraries for arbitrary-precision integers store numbers using multiple machine words. Let n be the bit length of the dividend, and m the bit length of the divisor. If n is at least m, elementary binary long division considers up to about n − m + 1 quotient bits. Each step may compare or subtract values with up to about m bits.
That gives the schoolbook bound
bit operations, which is often simplified to O(nm). When both operands have roughly n bits, this becomes O(n²). This is a bound for a basic division method, not a universal statement about every library: advanced algorithms can improve on schoolbook division for large operands, and real performance depends on implementation details.
If the divisor is a small fixed-size value but the dividend is an n-bit integer, the work can be linear in n: the algorithm processes the dividend’s digits while maintaining a small remainder. Thus even “big-integer modulo” does not have one bound independent of operand sizes.
Worked examples
For small fixed-width values, consider 123456 % 97. Since
the remainder is 72. If these values fit in the machine word, a typical algorithm analysis counts this as one constant-time operation.
Now suppose the dividend and divisor are both very large, around 2,048 bits each. A basic long-division analysis gives a worst-case scale of O(2,048²) bit operations, or about 4.2 million units in a simplified count. That number is not a prediction of actual runtime: it illustrates why the cost cannot be called constant as the operands grow. Optimized libraries may use faster methods, and their internal thresholds affect the result.
What to say in an algorithm analysis
Use a statement that matches your setting:
| Setting | Typical complexity statement |
|---|---|
| Fixed-width integers in a word-RAM model | O(1) per modulo operation |
| Arbitrary-precision integers with schoolbook division | O(nm) bit operations when n ≥ m |
| Arbitrary-precision integers with a fixed-size divisor | Often O(n) in the dividend bit length |
| Arbitrary-precision integers using an optimized library | Depends on the division algorithm and operand sizes |
If a program performs k modulo operations on fixed-width values, the total cost is O(k). For big integers, do not simply multiply the number of operations by a constant unless their sizes are bounded; account for how many bits each operation processes.
Common mistakes
- Calling every modulo operation O(1). That is a standard simplification for fixed-width operands, not for integers of unbounded size.
- Using the numeric value as the input size. Complexity is measured against representation length. An integer with value around 2ⁿ has only about n + 1 bits.
- Giving a single big-integer bound without specifying operand sizes. The dividend and divisor may have very different bit lengths.
- Confusing remainder conventions with runtime. Languages differ in how
%behaves for negative operands. That changes the result convention, not the main asymptotic cost. - Treating a sequence of remainder operations as one operation. For example, Euclid’s algorithm for the greatest common divisor uses repeated remainders; its total cost must account for the number and size of those steps.
For typical interview problems using ordinary int or long values, O(1) per % is the expected convention. For cryptography, symbolic computation, or other code using large integers, use a bit-complexity analysis instead.
References
- The Art of Computer Programming, Volume 2: Seminumerical Algorithms — Donald E. Knuth
Spotted an error? Send a correction. Read how we write and check articles in our editorial policy.