# Time complexity of number of solutions to equation of varying size, with varying upper-bound range restrictions

I solved this problem: Number of solutions to equation of varying size, with varying upper-bound range restrictions in Python by using generating functions. The solution is described in more detail in the comment section of David's answer here: https://stackoverflow.com/questions/69468913/given-n-balls-and-m-bins-each-bin-with-a-certain-capacity-how-many-combination/69470209?noredirect=1#comment122792101_69470209

I am wondering however, how does one calculate the time complexity of such a solution? Please explain it to me like you would to a child, if possible.

Is there any way to improve the time complexity? If so, how? I'm trying to think of a solution that includes memorization but cannot quite think of one. Any ideas?

Here is an $$O(mn)$$ algorithm. It appears different from the generating function approach, but it is "morally the same," while being easier to implement and describe the runtime of.

Note that the inclusion-exclusion approach described here takes something like $$O(m2^m)$$ time, so you should prefer to use that algorithm if $$n$$ is much larger than $$2^m$$.

You are given a list $$L=[C_1,C_2,\dots,C_m]$$ of the bin capacities, and want to count the number of solutions to $$\begin{cases} x_1+x_2+\dots+x_m=n \\ x_k\in \{0,1,\dots,C_k\}\text{ for each }k\in \{1,\dots,m\} \end{cases}$$ For each $$i\in \{1,\dots,m\}$$, and each $$j\in \{0,\dots,n\}$$, let $$F(i,j)=\text{ # of solutions to } \begin{cases} x_1+x_2+\dots+x_{\color{red}i}=\color{blue}j \\ x_k\in \{0,1,\dots,C_k\}\text{ for each }k\in \{1,\dots,m\} \end{cases}$$ That is, $$F(i,j)$$ is the number of solutions to the smaller problem where you only deal with the first $$i$$ variables, and the target sum is a possibly smaller number $$j$$. The overall goal is to compute $$F(m,n)$$.

The reason for considering $$F(i,j)$$ is the following: we have that $$F(i,j)=F(i-1,j)+F(i-1,j-1)+F(i-1,j-2)+\dots+F(i-1,j-C_i)\tag1$$ This follows by considering all possibilities for the variable $$x_i$$. If $$x_i=a$$, then the first $$i-1$$ variables have to add up to $$j-a$$, which can be done in $$F(i-1,j-a)$$ ways. The equation $$(1)$$ actually implies a simpler equation, which is better for computational purposes: $$F(i,j)=F(i,j-1)+F(i-1,j)-F(i-1,j-C_i-1)\tag2$$ As with any recursive equation, you need base cases: $$F(1,j)=\begin{cases}1 & 0\le j \le C_1 \\ 0 & \text{otherwise}\end{cases}\qquad\;\;\;\; \\ F(i,j)=0 \qquad \text{when j is negative}\tag3$$

Anyways, using equation $$(2)$$, and the base cases in $$(3)$$, you can compute $$F(m,n)$$ by filling out the $$m\times (n+1)$$ DP table whose entry in the $$i^{th}$$ row and $$j^{th}$$ column is $$F(i,j)$$.

• Wow, that's exactly what I needed. Thank you! Will try to implement it and get back. But a question about the generating function method being O(m * 2^m) - is that always the case? It doesn't seem like my implementation is the same, and if you look at the comment section to the accepted answer here: stackoverflow.com/questions/69468913/… David suggests that the time complexity is given by O(m*n)? Commented Oct 7, 2021 at 17:10
• @tmpquestionwonderer7777272 The $O(m2^m)$ is not for the generating function approach. It is for a different algorithm, which just computes the alternating sum of binomial coefficients described in that post I linked. Commented Oct 7, 2021 at 17:13
• Would you say O(m * n) is accurate for the generating function approach? Commented Oct 7, 2021 at 18:36
• @tmpquestionwonderer7777272 I would say the generating function approach is $O(m\cdot n\cdot C)$, where $C=\max_i C_i$. The idea is that you perform $O(m)$ polynomial multiplications, between two polynomials of degree $O(n)$ and $O(C)$. The $O(n)$ polynomial is the "accumulated polynomial", and the $O(C)$ one is $1+x+\dots+x^{C_i}$. This means my approach is faster if $C$ is large. Commented Oct 7, 2021 at 18:46
• Seeing as n = 10 * m in the worst case, can't we reduce the expression of the time complexity even further by saying that: O(m * n * C) = O(m * 10 * m * C) = O(m² * 10 * C). For small C (say less than or equal to 15), this could be reduced/simplified to O(m²). Is this an accurate way of reasoning, would you say? Commented Oct 7, 2021 at 19:33