Results 1 to 7 of 7
Like Tree2Likes
  • 1 Post By jim829
  • 1 Post By pbrockway2

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

  1. #1
    csanch11 is offline Member
    Join Date
    Oct 2013
    Posts
    63
    Rep Power
    0

    Default 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.

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

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

    Quote Originally Posted by csanch11 View Post
    Is there you think a much more efficient way of writing these codes?
    Java Code:
    int sum = (n*(n+1))/2;
    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  3. #3
    csanch11 is offline Member
    Join Date
    Oct 2013
    Posts
    63
    Rep Power
    0

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

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

    Default 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
    csanch11 likes this.
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  5. #5
    csanch11 is offline Member
    Join Date
    Oct 2013
    Posts
    63
    Rep Power
    0

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

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

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

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

    Quote Originally Posted by csanch11 View Post
    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
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

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

    Default 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
    jim829 likes this.

Similar Threads

  1. most efficient way to write xml
    By mondol in forum XML
    Replies: 1
    Last Post: 11-05-2013, 04:13 PM
  2. Tell me efficient way
    By lkalaivanan in forum New To Java
    Replies: 3
    Last Post: 08-11-2011, 11:36 AM
  3. is there a more efficient way?
    By Yakg in forum New To Java
    Replies: 3
    Last Post: 01-23-2011, 05:32 PM
  4. Need a simple and efficient solution.
    By Samgetsmoney in forum New To Java
    Replies: 9
    Last Post: 02-20-2009, 01:18 AM

Posting Permissions

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