How to find the matlab interp1 computational complexity?

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.

Bruno Luong 2023-10-31

编辑：Bruno Luong 2023-10-31

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

Kalasagarreddi Kottakota 2023-11-2

编辑：Kalasagarreddi Kottakota 2023-11-2

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))?

请先登录，再进行评论。