Modular Arithmetic Basics in DSA Python - Time & Space Complexity

Time Complexity: Modular Arithmetic Basics

O(1)

Understanding Time Complexity

We want to understand how the time to do modular arithmetic operations changes as numbers get bigger.

How does the number size affect the steps needed to find the remainder?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def mod_add(a, b, m):
    return (a + b) % m

result = mod_add(123456789, 987654321, 1000000007)
print(result)

This code adds two numbers and finds the remainder when divided by m.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Addition and modulo operation on integers.
• How many times: Only once per function call, no loops or recursion.

How Execution Grows With Input

As the numbers get bigger, the time to add and find remainder grows very slowly because these are simple operations.

Input Size (number of digits)	Approx. Operations
10 digits	Few basic steps
100 digits	More steps but still fast
1000 digits	More steps but grows slowly

Pattern observation: The time grows roughly proportional to the number of digits, not the number size itself.

Final Time Complexity

Time Complexity: O(1)

This means the operation takes constant time for normal fixed-size integers because addition and modulo are simple CPU instructions.

Common Mistake

[X] Wrong: "Modular arithmetic takes longer as numbers get bigger because the numbers are larger."

[OK] Correct: For fixed-size integers, addition and modulo are done in constant time by the processor, so size does not affect time.

Interview Connect

Understanding modular arithmetic time helps you explain why many algorithms use it for fast calculations with large numbers.

Self-Check

"What if we used very large numbers beyond normal integer size, like big integers? How would the time complexity change?"