Kernel estimate based classifiers are known to discriminate well in such demanding real-world applications as optical character recognition. However, in its basic form a kernel method often is too slow to use in an on-line pattern recognition system. One way to reduce the computational cost is to employ radial basis function expansions that use a small number of optimized kernels. A theoretically more tractable approach is data prebinning where the data are discretized on a mesh and a kernel estimator is formed using the bin centers. We report some new results on the integrated squared error of a binned kernel density estimator and discuss its computational complexity as measured by the average number of nonzero terms that need to be summed.