Time Complexity: Arithmetic operators
O(n)
0
0
Arithmetic operators in C++ - Time & Space Complexity
Understanding Time Complexity
We want to see how the time to run arithmetic operations changes as we do more of them.
How does the number of calculations affect the total time?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
int sum = 0;
for (int i = 0; i < n; i++) {
sum += i * 2 + 3;
}
return sum;
This code adds up a series of numbers calculated with simple arithmetic inside a loop.
Identify Repeating Operations
Look for loops or repeated calculations.
- Primary operation: The arithmetic calculation and addition inside the loop.
- How many times: Exactly once for each number from 0 up to n-1, so n times.
How Execution Grows With Input
Each time n grows, the number of calculations grows the same amount.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 10 calculations |
| 100 | 100 calculations |
| 1000 | 1000 calculations |
Pattern observation: The work 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: "Arithmetic operations inside a loop take constant time no matter how many times the loop runs."
[OK] Correct: Each arithmetic operation is fast, but doing many of them adds up, so total time grows with the number of loop runs.
Interview Connect
Understanding how simple calculations add up helps you explain how programs handle bigger data smoothly.
Self-Check
"What if we replaced the loop with two nested loops each running n times? How would the time complexity change?"