I have the following recurrence:
Let's say that I have 1 array f and 1 function g. A function call to g takes O(1) time. Note that we do not want to edit the code of function g, its a scipy function. I just want to compute the values in the f array using the recurrence given below:
For simplicity, one can assume that the function g is similar to the binomial coefficient function. So, just for simplicity, assume that g(n, i) = number of ways of choosing i items from n items where n >= i. Is it possible to solve this assuming we can modify g and make some kind of recurrence?
f[n] = summation(f[n-i]*g(i, n)) for i in [1, 2, 3, 4, ..., n]
Base Case: f[0] = 1.
If we use the above recurrence, it will take O(n^2) time. Any way to reduce it to O(n*log(n)) ?
Thanks in advance.