The problem of reconstructing an unknown signal from $n$ noisy samples can be addressed by means of nonparametric estimation techniques such as Tikhonov regularization, Bayesian regression and state-space fixed-interval smoothing. The practical use of these approaches calls for the tuning of a regularization parameter that controls the amount of smoothing they introduce. The leading tuning criteria, including Generalized Cross Validation and Maximum Likelihood, involve the repeated computation of the so-called equivalent number of parameters, a normalized measure of the flexibility of the nonparametric estimator. The paper develops new state-space formulas for the computation of the equivalent number of parameters in $O(n)$ operations. The results are specialized to the case of uniform sampling yielding closed-form expressions of the equivalent number of parameters for both linear splines and first-order deconvolution.