Understanding Loop Summation and Complexity in Java

Given code:

int sum = 0;

for (int i = 1; i < n; i++)
    sum = sum + i;





a) What is the value of sum after this code executes (in terms of n)?
Detailed Explanation:

The loop starts from i = 1 and continues while i < n.

In each iteration, it adds the current value of i to sum.

When i = n, the loop stops (since the condition is i < n, not i <= n).


So, the sum will be:
$$\text{sum} = 1 + 2 + 3 + ... + (n - 1)$$
This is the sum of the first $(n-1)\; positive\; integers.$
The formula for the sum of the first k positive integers:
$$\text{Sum} = \frac{k \cdot (k + 1)}{2}$$
Here, $k=n-1$
Therefore, the final value of sum is:
$$\boxed{\frac{(n - 1) \cdot n}{2}}$$


b) What is the complexity of the code assuming that adding two numbers always has O(1) complexity? Explain your answer.
Detailed Explanation:

The loop runs from i = 1 up to, but not including, i = n.

So, it executes (n - 1) times.

In each iteration, a constant-time operation (addition) is performed.


Therefore:

The number of operations grows linearly with n.

Each iteration is O(1).

Total time complexity = number of iterations × complexity per iteration = O(n).


In summary:

The overall time complexity of the code is O(n).

📩 Need a similar solution? Email me: adel455@hotmail.com