Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.