As you provide both formula you needed, then you can find what you need by following steps:
- Use O(n^2) to precompute nCr (as large as you need for n)
- Use repeating squaring method to precompute (1+x)^n (I suppose you know the domain of x? so it is O(n lgn) for all n
- Calculate A_n(X) as using those precomputed values, you have at most O(n) subproblems to calculate, each using O(n) which gives O(n^2)
EDITED:
For point #2, which is to calculate (1+x)^i(n-i) for i in [0,n], though the largest power can be up to n^2, but indeed there is only n instances, and we do not need to calculate all power up to n^2.
Let's write down the sequence of the power for different i in [0,n]: 0, n-1, 2(n-2), 3(n-3)...(n-1)(1)
And we can precompute them in a way like
function repeat_squaring(base, power){
//O(lg (power))
}
for(int i=0; i<=n; i++){
repeat_squaring(1+x, i*(n-i));
}
So now, what is the complexity to compute them in total? Just sum them up!
T = O(lg n + lg(2n) + lg(3n) + ... lg(n*n)) = O(summation(lg(i)) + nlg(n)) = O(lg(n!) + nlgn) = O(n lg n)
For the complexity of O(lg(n!)), there is two way to reason it, one is the famous Stirling's approximation, another way is this post: log(n!)
EDITED2: For shrinking n problem
I observe the pattern of the (1+x)^(i(N-i)) for N = n, n-1, n-2..etc
You can see that we can derive the term (1+x)^j for smaller A_n() from some already calculated (1+x)^(i(N-i))
We use O(n lg n) as described above to pre-calculate for the powers when N = n first, also we can use O(n lg n) to pre-calculate all (1+x)^i for i in [0..n]
Now as the pattern shown, the term (1+x)^(i(N-i)) for consecutive N values (n vs n-1, n-1 vs n-2 ...), you can indeed use O(1) to multiply / divided by some (1+x)^i where i in [0..n] (depends on your implementation, either bottom-up / top-down)
So I still think you only need O(n lgn) to pre-compute those powers, and use O(1) to transform them into other powers dynamically when you needed. (You can think as you are doing dynamic programming on both (1+x)^(i(N-i)) and A_i() at the same time)
TL;DR
Of course, if you do not want things being too complicated, you can just use O(n^2) to do a separate DP on (1+x)^(i(N-i)) for all N in [1..n]
// High Level Psuedo Code
var nCr[][];
var p[]; // (1+x)^0, (1+x)^1 ... (1+x)^n
var b[]; // (1+x)^0, (1+x)^(n-1), (1+x)^2(n-2)...
var power[n][i] // (1+x)^i(n-i), power[max_n][x] = b[] actually
var A[] // main problem!
Precompute nCr[][]; // O(n^2)
Precompute p[]; // O(n lg n)
Precompute b[]; // O(n lg n)
Precompute power[n][i] {
// O(n^2)
for all x, for all i
power[x][i] = power[x+1][i]/p[i]
}
Compute A using all those precompute arrays, O(n^2)
