I'm trying to do a time complexity analysis of MATLAB's cubic spline algorithm. I have a 1000 x 1000 table and I want to know what is being done when I query a point that is in between two quantities from that table. As such, I'd like to break it up into individual steps so that I can find the big $O$ notation for each of those steps.
I've seen a lot of stuff online, such as this, but they assume knowledge of the slopes at the end points. If that is necessary, I'm assuming MATLAB has some steps where it computes the slope using the previous and later points. Does anyone have any insight on this?
I’m not familiar with Matlab’s spline functions. But I think they are just an implementation of the algorithms described in Carl deBoor’s book “A Practical Guide to Splines”.
If the Matlab functions don’t accept initial and final slopes as input, they need to get two additional linear equations from somewhere else. Typically, people use the “natural end condition” constraint, or the “not a knot” constraint to get the two additional equations. These are both described on the Wikipedia page you referenced.
But, anyway, the construction of two additional equations is insignificant compared to all the work that goes into solving the linear system. So, I think your big O analysis only needs to consider the latter. The linear system is banded (tridiagonal) so it can be solved in O($n$) time, where $n$ is the number of interpolated points.