Arithmetic operators and overflow in Swift - Time & Space Complexity

Time Complexity: Arithmetic operators and overflow

O(n)

Understanding Time Complexity

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

How does using operators like + or * affect the speed when numbers grow large?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

var total = 0
for i in 1...n {
    total = total &+ i  // &+ is overflow addition in Swift
}
print(total)
    

This code adds numbers from 1 up to n using overflow addition.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Addition with overflow (&+)
• How many times: The addition happens once for each number from 1 to n, so n times.

How Execution Grows With Input

As n grows, the number of additions grows the same way.

Input Size (n)	Approx. Operations
10	10 additions
100	100 additions
1000	1000 additions

Pattern observation: The number of operations grows directly with n, so doubling n doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line as the input size grows.

Common Mistake

[X] Wrong: "Overflow operations take longer because they check for overflow every time."

[OK] Correct: Overflow operators in Swift do the addition in constant time, just like normal addition, so the time per operation does not increase.

Interview Connect

Understanding how simple arithmetic operations scale helps you reason about performance in many programs, especially when working with large data or loops.

Self-Check

"What if we replaced the loop with a recursive function doing the same additions? How would the time complexity change?"