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