fakeac's blog

How to speed up this DP?
By fakeac, history, 6 years ago, In English

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.

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Vector multiplication using FFT.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi tutis, I have updated the problem statement. Please take a look.

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have updated the problem statement, please take a look.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by fakeac (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by fakeac (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like 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.

→ Reply
»
6 years ago, # |
  Vote: I like it -22 Vote: I do not like it

Maybe fast IO can help :)

→ Reply