# Thread: Is this the most efficient solution for taking the sum?

1. Member Join Date
Oct 2013
Posts
63
Rep Power
0

## Is this the most efficient solution for taking the sum?

Here are two methods, iterative and recursive, which calculates the sum of all positive integers between 1 and a given integer n (input into the method). We know that as n gets larger, the solution takes longer to solve. Is there you think a much more efficient way of writing these codes?

NOTE: I'VE CROSS POST HERE Is this the most efficient solution for taking the sum? (Beginning Java forum at JavaRanch)
I'll let everyone know whether my answer is resolved from the other forum so I don't waste anybody's time. Thanks!

Iterative Method:
Java Code:
```public static int iterativeSum(int n) {
int sum = 0;
if ((n == 0) || (n == 1)) {
return n;
}

for (int i = 0; i < n ; n--) {
sum = sum + n;
}

return sum;
}```

Recursive Method:
Java Code:
```
public static int recursiveSum(int n) {
int sum = 0;
if ((n == 0) || (n == 1)) {
return n;
} else {
sum = recursiveSum(n-1) + n;
}
return sum;```
Last edited by csanch11; 11-15-2015 at 07:44 PM.  Reply With Quote

2. Senior Member Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
6,226
Rep Power
14

## Re: Is this the most efficient solution for taking the sum? Originally Posted by csanch11 Is there you think a much more efficient way of writing these codes?
Java Code:
`int sum = (n*(n+1))/2;`
Regards,
Jim  Reply With Quote

3. Member Join Date
Oct 2013
Posts
63
Rep Power
0

## Re: Is this the most efficient solution for taking the sum?

Hey jim, I would have never thought of that. Is that some sort of formula that you look up, or does it come from experience?  Reply With Quote

4. Senior Member Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
6,226
Rep Power
14

## Re: Is this the most efficient solution for taking the sum?

Experience based on math courses. Probably algebra or whenever one learns about summation of infinite and finite series (both arithmetic and geometric series). Here is how it's derived.

S = 1 + 2 + 3 + 4 + 5 + ..... + n
S = n + n-1 + n-2 + n-3 + n-4 + ......+ 1

Add each column of corresponding terms.

2S = 1+n + 1+n + 1+n + 1+n + .....................1+n (and since you have n of these)
2S = n(1+n) now divide by 2

S = n(1+n)/2

And as a bonus, if you square the above formula, you get the sum of consecutive cubes from 1 to n.

Regards,
Jim  Reply With Quote

5. Member Join Date
Oct 2013
Posts
63
Rep Power
0

## Re: Is this the most efficient solution for taking the sum?

Why did S = 1 + 2 + 3 turn into n + n -1 + n-2 ???  Reply With Quote

6. Senior Member Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
6,226
Rep Power
14

## Re: Is this the most efficient solution for taking the sum? Originally Posted by csanch11 Why did S = 1 + 2 + 3 turn into n + n -1 + n-2 ???
Because I am rewriting the sum in reverse.

s = 1 + 2 + 3
s = 3 + 2 + 1

2s = 4 + 4 + 4
2s = 3(4)
s = 6

Regards,
Jim  Reply With Quote

7. Moderator   Join Date
Feb 2009
Location
New Zealand
Posts
4,716
Rep Power
18

## Re: Is this the most efficient solution for taking the sum?

> (Jim) And as a bonus, if you square the above formula, you get the sum of consecutive cubes from 1 to n.

Wikipedia gives a lovely picture proof of this: https://upload.wikimedia.org/wikiped...rem_3D.svg.png   Reply With Quote

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•