How to find the matlab interp1 computational complexity?

Hi,

I am trying find the computational complexity of interp1 with 'linear', and "cubic". Can I get some help regarding this?

I am thinking it is O(n) and O(n^3). Are these correct?

[Bruno Luong]

"Are these correct?"

No, O(n^3) is completely off (over estimated), see my answer. Also you don't tell what n is.

Answer 1

[Bruno Luong]

If N is the number of data points (x, y), M is the query points (xq)

interp1(x, y, xq, ...)

has complexity of O(M*log(N)) for all methods, if x is sorted.

Essentially it is the time of query where xq are located in subintervals. Time of interpolation value are constant per point even for spline method.

If x is not sorted then you need to add log(N) of sorting but then the O notation remains the same

[Kalasagarreddi Kottakota]

Hi @Bruno Luong,

Thank you for the reply. May I ask you : how did you arrive at the complexity O(M*log(N)) ?

[Bruno Luong]

As I wrote : "Essentially it is the time of query where xq are located in subintervals. Time of interpolation value are constant per point even for spline method."

There is a recent discussion here https://www.mathworks.com/matlabcentral/answers/1994703-why-is-it-so-fast-to-calculate-one-dimensional-cubic-spline-interpolation-through-matlab?s_tid=srchtitle

[John D'Errico]

@Kalasagarreddi Kottakota

Easy.

O(M*log(N))

You have M points to interpolate. Think of it as a loop on the number of points to interpolate. So if one point takes O(log(N)) time, then M points take M times that.

Where does the log(N) come from? That is simply the time required to identify which bin a point lies in. Once you know which bin interval a point lies in, the interpolation time is constant, requiring only a few adds and multiplies.

So the linear case is trivial then.

As far as the other methods go, they are also pretty easy, since the time to actually generate the coefficients for a cubic interpolant is low. For a pchip interpolant, for example, that time is linear in N. So unless N is very large, and M relatively small, the time is dominated by the actual evaluation time, and you can ignore the time required to compute the spline coefficients themselves. This is true even for a spline interpolant.

Finally, a spline interpolant is not going to be O(N^3) to generate the spline coefficients anyway, unless you use something silly like Gaussian elimination with a full matrix. That is just a bad idea for several reasons.

[Kalasagarreddi Kottakota]

Hi @Bruno Luong,

In the above answer, is it log10 or log2. Does matlab internally considers log2 or log10?

[Bruno Luong]

doesn't matter for O notation, since log 10, log 2 theirs inverse are constants

[Kalasagarreddi Kottakota]

Hi @John D'Errico,

Just a query about log(N): is the time required to identify which bin a point lies in.

Does in matlab, or every operation, does log(N) exists?. Like for example, I have a discrete signal p(n), with n=1,...,N. Now lets say I advance by a constant n0 samples, like p(n+n0) for all samples in signal p. Does in matlab, the complexity is O(N) as it is addition complxeity applied for N samples or O(N*log(N))?

[Kai Angermueller]

if you actually try running interp1 with various N and tic/toc the run time, you'll find it's actually O(M*N) for sorted :( This is terrible. It's also strange that it's O(M*N) whether you are searching for xq near the bottom end of x, the middle, or near the top end of x. So it's not just doing a linear serach. But it's also not scaling like any sort of binary/tree search. Strange and bad.