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.
Vector multiplication using FFT.
Hi tutis, I have updated the problem statement. Please take a look.
Not sure I understand the statement, what would f(1) be? To me it seems like f(1) = 0 and consequently f(n) = 0 for any n.
EDIT: Thanks for clarifying. Do I understand that g takes two arguments? Then nothing better than O(N2) is possible because we need to know the value of g for all those different pairs of arguments.
I have updated the problem statement, please take a look.
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?
Auto comment: topic has been updated by fakeac (previous revision, new revision, compare).
Auto comment: topic has been updated by fakeac (previous revision, new revision, compare).
It seems that the upper bound for i should be n instead of n - 1, as the n-th value of f, where n > 0, should depend on the initial value f(0) as well.
The first three iterations when n = 1, 2, 3 should be
f(1) = f(0)g(1)
f(2) = f(1)g(1) + f(0)g(2)
f(3) = f(2)g(1) + f(1)g(2) + f(0)g(3)
and the final value should be
f(n) = f(n - 1)g(1) + f(n - 2)g(2) + ... + f(0)g(n)
This should be computed efficiently using discrete convolution, see section fast discrete convolution in Convolution for more details.
Have corrected it.
It seems like the lower bound is O(n^2) because f[n] depends on O(n^2) values of g and each one of them has to be found in O(1). However, a better solution may exist if g is the binomial coefficient.
https://codeforces.com/blog/entry/59452
Maybe fast IO can help :)
MIT wants to know your location