0
$\begingroup$

My question is inspired by the following problem:

Given $k$ coins with denominations $\{c_1, ..., c_k\}$, how many ways are there to generate $n$ cents?

This can be solved in $\Theta(nk)$ time using dynamic programming. But can also be solved by finding the coefficient of $x^n$ in the generating function $\prod_{i \leq k} \frac{1}{1-x^{c_i}}$

What is the time complexity of such an approach?

How is the time complexity related to which generating function is solved for?

1 Answers 1

3

If you're willing to make the complexity worse in $k$ you can make it substantially better in $n$. Suppose we want to extract the coefficient $a_n$ of $x^n$ in the generating function $\frac{P(x)}{Q(x)}$ where $Q$ is a polynomial of degree $d$ with nonzero constant term and $\deg P < \deg Q$. Then, as it turns out, we can write down a $d \times d$ matrix $M$ (the companion matrix of the polynomial whose coefficients are the reverse of $Q$'s) and vectors $v, w$ such that $a_n = v^T M^n w.$

So the problem reduces to the efficient computation of powers of a matrix, and this can be done efficiently by binary exponentiation. This uses $O(\log n)$ matrix multiplications, but unfortunately the sizes of the entries in general grow exponentially in $n$.

However, in this case the sizes of the entries grow polynomially in $n$, so the final time complexity is polynomial in both $d$ and $\log n$.

Example. Let $\frac{P(x)}{Q(x)} = \frac{x}{1 - x - x^2}$ be the generating function for the Fibonacci numbers $F_n$. Then, as it turns out, the matrix we want is $M = \left[ \begin{array}{cc} 1 & 1 \\\ 1 & 0 \end{array} \right]$, and it satisfies $M^n = \left[ \begin{array}{cc} F_{n+2} & F_{n+1} \\\ F_{n+1} & F_n \end{array} \right].$

The binary exponentiation strategy above corresponds to repeated use of the duplication formulas $F_{2n} = F_{n+1}^2 + F_n^2$ $F_{2n+1} = F_{n+2} F_{n+1} + F_{n+1} F_n$

both of which follow directly from the identity $M^{2n} = (M^n)^2$.


I should also mention that for fixed $k$ you can in fact write down an explicit quasi-polynomial closed form for the answer, so you just need an efficient algorithm for integer multiplication.