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

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)?

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)


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.

• Thank you! How would the Gauss sum be calculated in a recursive way? Can you provide an example? Apr 5, 2022 at 21:25
• Apr 5, 2022 at 21:35
• It’s one addition and one multiplication to get the complete result. No recursion anywhere in sight. Apr 6, 2022 at 6:07
• The Gauss story might be apocryphal. Apr 6, 2022 at 15:45

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)