Problem of the Day

Tuesday, May 12, 2026

Problem:

Two software developers each write a small static method designed to sum the integers from 1 to n, inclusive. Consider the code from the first developer, which returns the correct result.

/**
 * Adds the integers from 1 - n, inclusive
 */
public static int sum1(int n)
{
    int sum = 0;
    for (int i = 1; i <= n; i++)
        sum += i;
    return sum;
}

The second developer writes the method shown here, which also returns the correct result.

/**
 * Adds the integers from 1 - n, inclusive
 */
public static int sum2(int n)
{
    return n * (n + 1) / 2;
}

Preliminary tests of the methods reveal that they both run very quickly, adding up thousands of numbers in less than a millisecond.

Which is the preferred method, sum1 or sum2, with regards to their Big-O performance?

1. The methods have the same Big-O performance, so the easier to understand method, sum1, is better.
2. The methods have the same Big-O performance, so the shorter method, sum2, is better.
3. The Big-O performance of the two algorithms is the same, so neither one is preferred.
4. The Big-O performance of sum1 is O(n) (linear), so it is the better method.
5. The Big-O performance of sum2 is O(1) (constant), so it is the better method.

Show solution: