How to estimate the number of recursive calls

[nuzzle]

I took just a second on an ordinary desktop. Quite amazing.

Just for fun I've optimized the code in my previous reply.

It's based on two features. First, Pascal's triangle is symmetrical so only one half needs be calculated. Second, the recurrence algorithm works also with a cumulative Pascal's triangle without additional cost. Cumulative means that each number in the triangle is no longer an individual binominal but the sum of all binominals to the left on the same row. This means that not all numbers in the subtriangle needs be summed anymore, only the number at the far right on each row (because it's in effect the row sum).

These changes together speed up the algorithm about 4 times. So f(2000,1000) for example which took about 1 second before now takes 1/4 of a second. To push it a little I tried f(10000,5000). It's an enormous integer with about 3000 digits. It took just 40 seconds.

Here's the optimized code.

import java.math.BigInteger;
import java.util.ArrayList;

public class Main {

		// the rows of Pascal's cumulative triangle one by one
	static class PascalRows {
		public PascalRows() {row.add(BigInteger.ONE);}
		public int size() {return n+1;}
		public BigInteger get(int i) { // now "virtual" access to row numbers
			if (i+i <= n) return row.get(i); // left row half
			i = n-i-1;
			return (i<0) ? pow : pow.subtract(row.get(i)); // right row half
		}
		public void nextRow() {
			n++;
			pow = pow.shiftLeft(1);
			BigInteger f = row.get(0);
			final int L = row.size();
			for (int i=1; i<L; i++) { // same recurrence now generates cumulative row
				final BigInteger s = row.get(i);
				row.set(i, f.add(s));
				f = s;
			}
			if ((n & 1) == 0) row.add(pow.subtract(row.get(L-1))); // row middle number
		}
		private int n = 0; // row number
		private BigInteger pow = BigInteger.ONE; // known row sum
		private final ArrayList<BigInteger> row = new ArrayList<BigInteger>();  
	}
		// sum of all binominals of a subtriangle of Pascal's triangle
	static BigInteger subTriangle(int n, int k) {
		BigInteger sum = BigInteger.ZERO;
		final PascalRows pascal = new PascalRows();
		for (int i=0; i<k; i++) pascal.nextRow();
		for (int i=0,L=n-k-1; i<L; i++) {
			pascal.nextRow();
			sum = sum.add(pascal.get(i)); // no row loop, instead rightmost number added
		}
		return sum;
	}
		// f(n,k) = 2 * (2^n - subTriangle(n,k)) - 1
	static BigInteger f(int n, int k) {
		return BigInteger.ONE.shiftLeft(n).subtract(subTriangle(n,k)).shiftLeft(1).subtract(BigInteger.ONE);
	}
	
	public static void main(String[] args) {
		System.out.println("Hello World!");
		long start = System.nanoTime();
		System.out.println(f(2000,1000));
		long stop = System.nanoTime();
		System.out.println("time: " + (stop - start)*0.000000001 + " seconds");
	}
}