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?