I have the following recurrence:

Let's say that I have 2 arrays f and g such that all values of the g array are already computed. I just want to compute the values in the f array using the recurrence given below:

f(n) = summation(f(n — i)*g(i)) for i in [1, 2, 3, 4, ..., n — 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.