Count the Operations in a Summing Loop

Easy10 min

Topics

BasicsComplexity

Companies

TCSInfosysWipro

For the loop that adds the numbers 1 to n, return [sum, comparisons, additions, increments]: the sum it computes, how many times the condition i <= n is checked, how many additions into the sum happen, and how many times i is increased. Complexity analysis starts by counting basic operations — comparisons, additions, assignments — instead of timing a program with a stopwatch. Counting is independent of how fast a particular computer is, so it describes the algorithm itself.

Test Case 1:

Input:n = 3

Output:[6, 4, 3, 3]

Explanation:The loop i = 1..3 sums to 6, checks i <= n four times (the last check fails), does 3 additions and 3 increments.

Test Case 2:

Input:n = 0

Output:[0, 1, 0, 0]

Explanation:The condition is checked once, fails, and nothing else runs.

Constraints

◆0 ≤ n ≤ 10000

Try the Dry Run

Mode

Approach

Approach & Solutions

Instrument the Loop with CountersGood

Take the loop "for i from 1 to n, add i to sum" and attach a counter to each kind of basic operation: one for every check of i <= n, one for every addition into sum, one for every increment of i. Running the loop then reports exactly how much work it did.

TimeO(n)

SpaceO(1)

Java

Try it out

class Solution {
    public int[] operationCounts(int n) {
        int sum = 0, comparisons = 0, additions = 0, increments = 0;
        int i = 1;
        comparisons++;
        while (i <= n) {
            sum += i;
            additions++;
            i++;
            increments++;
            comparisons++;
        }
        return new int[] {sum, comparisons, additions, increments};
    }
}

Count with FormulasOptimal

Once you see the pattern, the counts follow directly: the body runs n times, so there are n additions and n increments, and n + 1 condition checks. The sum itself is n(n + 1) / 2. Counting operations this way — without running the code — is exactly what complexity analysis does.

TimeO(1)