Arithmetic operators - Time & Space Complexity

Time Complexity: Arithmetic operators

O(n)

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 = sum + i;
}
return sum;
    

This code adds numbers from 0 up to n-1 using a loop.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Addition inside the loop
• How many times: Exactly n times, once per loop cycle

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 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 they run."

[OK] Correct: Each operation takes a small fixed time, but doing many operations adds up, so total time grows with the number of operations.

Interview Connect

Understanding how simple arithmetic inside loops affects time helps you explain how programs scale and run efficiently.

Self-Check

"What if we replaced the addition with a multiplication inside the loop? How would the time complexity change?"

Practice

1. Which arithmetic operator in C gives the remainder of a division?

easy

A. The multiplication operator (*)

B. The division operator (/)

C. The modulus operator (%)

D. The subtraction operator (-)

Solution

1. Step 1: Understand the modulus operator

   The modulus operator (%) returns the remainder after division of two integers.

2. Step 2: Compare with other operators

   Division (/) returns the quotient, multiplication (*) multiplies, subtraction (-) subtracts.

3. Final Answer:

   The modulus operator (%) -> Option C

4. Quick Check:

   Remainder = % operator [OK]

Hint: Remainder means modulus (%) operator [OK]

Common Mistakes:

• Confusing division (/) with modulus (%)
• Thinking multiplication (*) gives remainder
• Using subtraction (-) for remainder

2. Which of the following is the correct syntax to multiply two integers a and b in C?

easy

A. a x b;

B. a * b;

C. a . b;

D. a & b;

Solution

1. Step 1: Recall multiplication operator in C

   The multiplication operator in C is the asterisk symbol (*).

2. Step 2: Check each option

   a * b; uses '*', which is correct. Options B, C, D use invalid symbols for multiplication.

3. Final Answer:

   a * b; -> Option B

4. Quick Check:

   Multiply with * operator [OK]

Hint: Use * for multiplication in C [OK]

Common Mistakes:

• Using 'x' instead of '*' for multiplication
• Using '.' or '&' mistakenly
• Missing semicolon at end

3. What is the output of this C code?

int a = 7, b = 3;
printf("%d", a / b);

medium

A. 1

B. 2.333333

C. 3

D. 2

Solution

1. Step 1: Understand integer division in C

   Both a and b are integers, so a / b performs integer division, which discards the decimal part.

2. Step 2: Calculate 7 / 3 using integer division

   7 divided by 3 is 2.333..., but integer division returns 2.

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Integer division truncates decimals [OK]

Hint: Integer division drops decimals, result is integer [OK]

Common Mistakes:

• Expecting floating-point result
• Confusing remainder with division result
• Using wrong format specifier in printf

4. Find the error in this C code snippet:

int x = 10;
int y = 3;
int z = x / y.0;
printf("%d", z);

medium

A. Using a floating-point number in integer division

B. Incorrect format specifier in printf

C. Missing semicolon after variable declaration

D. Division by zero error

Solution

1. Step 1: Analyze the division expression

   The expression x / y.0 uses y.0 which attempts a floating-point literal but causes invalid syntax, as x and y are integers.

2. Step 2: Understand the syntax error

   Using y.0 causes a compilation error due to invalid syntax in the integer division context.

3. Final Answer:

   Using a floating-point number in integer division -> Option A

4. Quick Check:

   Integer division must use integers only [OK]

Hint: Integer division needs integer operands only [OK]

Common Mistakes:

• Thinking printf format is wrong
• Ignoring the decimal in y.0
• Assuming division by zero

5. You want to calculate the average of two integers a and b in C and get a floating-point result. Which code snippet correctly does this?

hard

A. float avg = (a + b) / 2.0;

B. float avg = (a + b) / 2;

C. int avg = (a + b) / 2.0;

D. float avg = a / b + 2;

Solution

1. Step 1: Understand integer vs floating-point division

   Dividing by 2 (integer) causes integer division, losing decimals. Dividing by 2.0 (double) forces floating-point division.

2. Step 2: Check each option for correct average calculation

   float avg = (a + b) / 2; does integer division then converts to float, losing decimals. float avg = (a + b) / 2.0; divides by 2.0, giving float result. int avg = (a + b) / 2.0; stores float result in int, losing decimals. float avg = a / b + 2; is incorrect formula.

3. Final Answer:

   float avg = (a + b) / 2.0; -> Option A

4. Quick Check:

   Divide by 2.0 for float average [OK]

Hint: Divide by 2.0 to get float average [OK]

Common Mistakes:

• Dividing by integer 2 causing integer division
• Storing float result in int variable
• Wrong formula for average