Problem of the Day

Thursday, April 24, 2025

Problem:

The following method uses recursion to add the numbers from 1 to n.

/**
 * Method sums the numbers from 1 to n using recursion.
 * @param n the upper value (inclusive) to be summed
 * @return the sum of integers 1 to n
 * PRECONDITION: n >= 0
 */
public static int sum(int n)
{
    if (n == 0)
        return 0;
    else
        return n + sum1(n - 1);
}

If each assignment operation (=), math operation (+), and return operation take a unit of time, the time-complexity can be shown to be

T(n) = 5n - 3

What is the corresponding Big-O performance of this method?

O(1)
O(5)
O(n)
O(5n)

Show solution:

The correct answer is c. The expression "Big-O" refers to the order of the most important term in the time-complexity polynomial. In this case, with

T(n) = 5n - 3

the constant of 3 is removed from consideration, with the 5n term including an n¹. Therefore, Big-O for this method is O(n).

(Note that the subject of classifying algorithms by their time- or space-complexity goes well beyond this simple description, but this treatment is sufficient for the AP Computer Science A curriculum.)