Counting the solutions to a restricted 0-1 knapsack problem
There are almost-matching lower and upper bounds for the running time of the best algorithm for this problem, considered as a function of $n$.  In particular, we can prove that the complexity is $\Omega(n)$ and $O(\text{poly}(n))$, when considered only as a function of $n$.

For the upper bound, there's an algorithm whose running time is polynomial in $n$.  Without loss of generality we can take $k \le n$ (for terms where $i&gt;n$ contribute nothing to the sum).  Also you can compute ${n \choose i}$ in time polynomial in $n$.  Therefore, the whole sum can be evaluated in time polynomial in $n$.  In other words, it's solvable in pseudo-polytime.

The size of the output can be as large as $2^n$ (e.g., where $k=n$), so the output can take $\Theta(n)$ bits to represent.  This is exponential in the size of the input.  Thus, any algorithm for the problem must have worst-case running time at least $\Omega(n)$.