1
$\begingroup$

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

$\endgroup$
1

3 Answers 3

0
$\begingroup$

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)
$\endgroup$
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thank you! How would the Gauss sum be calculated in a recursive way? Can you provide an example? $\endgroup$
    – maxig
    Apr 5, 2022 at 21:25
  • $\begingroup$ @maxig physicsdb.com/sum-natural-numbers $\endgroup$ Apr 5, 2022 at 21:35
  • $\begingroup$ It’s one addition and one multiplication to get the complete result. No recursion anywhere in sight. $\endgroup$
    – gnasher729
    Apr 6, 2022 at 6:07
  • 1
    $\begingroup$ The Gauss story might be apocryphal. $\endgroup$ Apr 6, 2022 at 15:45
1
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.