Computational complexity of spline interpolation

The procedure for composing the spline function of order m that interpolates n data is roughly divided into two stages: (1) constructing the matrix An that transforms the fl-spline coefficient vector c into the sample value vector s; and (2) calculating the vector c. Then the effects of boundary conditions and the locations of the sampling points and the knots on the number of computations for spline interpolation are evaluated. There are no boundary condition effects of the construction of A" for equispacing. Non-periodic boundary conditions reduce the number of computations needed to calculate c from O(m2n) to O(m2n/4). In the construction of An, choosing equispaced sampling points reduces the number of computations from O(m2n) to O(m2) in the case of sampling points located at a constant interval between each pair of adjacent knots. In the calculation of c, equispaced sampling points reduce the number of computations from O(m2n) to O(m2n /2) in the case where m is even and the locations of the knots are identical with those of the sampling points.