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.

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

Kai Angermueller 2025-4-9

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.

请先登录，再进行评论。

How to find the matlab interp1 computational complexity?

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

采纳的回答

7 个评论
显示 5更早的评论隐藏 5更早的评论

更多回答（0 个）

另请参阅

类别

标签

Community Treasure Hunt

How to find the matlab interp1 computational complexity?

1 个评论 显示 -1更早的评论隐藏 -1更早的评论

采纳的回答

7 个评论 显示 5更早的评论隐藏 5更早的评论

更多回答（0 个）

另请参阅

类别

标签

Community Treasure Hunt

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

7 个评论
显示 5更早的评论隐藏 5更早的评论