Filter löschen
Filter löschen

How to find the matlab interp1 computational complexity?

7 Ansichten (letzte 30 Tage)
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?
  1 Kommentar
Bruno Luong
Bruno Luong am 26 Okt. 2023
"Are these correct?"
No, O(n^3) is completely off (over estimated), see my answer. Also you don't tell what n is.

Melden Sie sich an, um zu kommentieren.

Akzeptierte Antwort

Bruno Luong
Bruno Luong am 26 Okt. 2023
Bearbeitet: Bruno Luong am 26 Okt. 2023
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
  6 Kommentare
Bruno Luong
Bruno Luong am 31 Okt. 2023
Bearbeitet: Bruno Luong am 31 Okt. 2023
doesn't matter for O notation, since log 10, log 2 theirs inverse are constants
Kalasagarreddi Kottakota
Kalasagarreddi Kottakota am 2 Nov. 2023
Bearbeitet: Kalasagarreddi Kottakota am 2 Nov. 2023
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))?

Melden Sie sich an, um zu kommentieren.

Weitere Antworten (0)

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by