Java Sigma Equation Solving sigma(i=1 to k)((-1)^i+1)(i)(i+1) Timedout for long values

Question

Getting timedout error while calculating the value of sigma notation sigma(i=1 to k)((-1)^i+1)(i)(i+1) for very long values example :10^8 .Can any one guide me where I am doing wrong

import java.io.*;
import java.util.*;


public class TestClass {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter wr = new PrintWriter(System.out);
        int T = Integer.parseInt(br.readLine().trim());
        for(int t_i=0; t_i<T; t_i++)
        {
            int params1 = Integer.parseInt(br.readLine().trim());

            long out_ = maxValueX(params1);
            System.out.println(out_);
            System.out.println("");
         }

         wr.close();
         br.close();
    }
    static long maxValueX(long params1){
        long sum=0;
       for(long i=1;i<=params1;i++){
           sum=(long)Math.pow(-1,i+1)*i*(i+1)+sum;
       }
       return sum;

    }
}

Answer 1

The trick is to simplify that sigma expression. If params1 is even:

1*2 - 2*3 + 3*4 - 4*5 + 5*6 - 6*7 + ... =
(1*2 - 2*3) + (3*4 - 4*5) + (5*6 - 6*7) + ... =
2*(1-3) + 4*(3-5) + 6*(5-7) + ... =
-2*2 + -2*4 + -2*6 + ... =
-2*2*(1 + 2 + 3 + ...)

Now, there is a closed-form formula for the parenthesized term, so you don't even need to compute it iteratively: https://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF

This approach also works for an odd params1, except that there'll be an extra term at the end that needs to be accounted for.

With some further algebraic manipulations (left as an exercise for the reader), one can derive a single formula that works for both odd and even arguments. In pseudo-code (that happens to be valid Python):

def linear_time(n):
  return sum((-1)**(i+1)*i*(i+1) for i in range(1, n+1))

def constant_time(n):
  return (-1)**n * (-n*n//2 - n)

for n in (100, 101, 120, 100000, 1297981):
  print linear_time(n), constant_time(n)

(That exponentiation is just a lazy shortcut for computing the sign; we don't actually need to compute the exponent for that.)