Recursive algorithm for adding numbers from 1 to n with O(1) time complexity

Question

So I have a recursive algorithm which sums up the numbers from 1 to n plus one (hence the return 1):

public static int S(int n) {
    if(n < 0) {
        return 1;
    }
    else {
        return n + S(n-1);
    }
}

This algorithm has a time complexity of O(n).

Is it possible to derive an algorithm which produces the same output as the one shown above but with a constant time complexity of O(1)?

Answer 1

The sum $1+2+3+\cdots+n$ is equal to $n(n+1)/2$; hence, the following function would return the same output:

Function S(n):
    if n < 0, then return 1
    Else return n(n+1)/2 + 1

It takes time $O(1)$, but does not make recursive function calls. Generally, a recursive function would take linear time, unless you are willing to consider contrived versions like the code shown below, where the depth of recursion is bounded by a constant:

Function S(n):
    If n is even, then return 1+n(n+1)/2
    Else return n + S(n-1)

Answer 2

Yes. The method was invented by Carl Friedrich Gauss, aged 6. It’s simple. Add the first and the last number. Add the second and the second-to-last number. Then the third and third to last. And so on. Find the pattern.

Answer 3

Any algorithm that has $O(1)$ complexity must be extremely simple.

In your case, there is just a known closed form for this summation, so your program can return it within $O(1)$ (well technically this is assuming that addition, multiplication and division can be done in constant time)