The problem of reconstructing an unknown signal from n noisy samples can be addressed by means of non- parametric estimation techniques such as Tikhonov reg- ularization, Bayesian regression and state-space fixed- interval smoothing. The practical use of these ap- proaches calls for the tuning of a regularization param- eter that controls the amount of smoothing they intro- duce. The leading tuning criteria, including Generalized Cross Validation and Maximum Likelihood, involve the repeated computation of the so-called equivalent num- ber of parameters, a normalized measure of the flexi- bility of the nonparametric estimator. The paper de- velops 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 sam- pling yielding closed-form expressions of the equivalent number of parameters for both linear splines and first- order deconvolution.