Editing Dynamic time warping (section)

==Complexity==
The time complexity of the DTW algorithm is <math>O(NM)</math>, where <math>N</math> and <math>M</math> are the lengths of the two input sequences. The 50 years old quadratic time bound was broken in 2016: an algorithm due to Gold and Sharir enables computing DTW in <math>O({N^2}/\log \log N)</math> time and space for two input sequences of length <math>N</math>.<ref>
{{cite journal |last1=Gold |first1=Omer |last2=Sharir |first2=Micha |title=Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier |journal=ACM Transactions on Algorithms|date=2018 |volume=14 |issue=4 |doi=10.1145/3230734 |s2cid=52070903 }}</ref> 
This algorithm can also be adapted to sequences of different lengths. Despite this improvement, it was shown that a strongly subquadratic running time of the form <math>O(N^{2-\epsilon})</math> for some <math>\epsilon > 0</math> cannot exist unless the [[Strong exponential time hypothesis]] fails.<ref>{{Cite book|chapter-url=https://doi.org/10.1109/FOCS.2015.15|doi=10.1109/FOCS.2015.15|chapter=Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping|title=2015 IEEE 56th Annual Symposium on Foundations of Computer Science|year=2015|last1=Bringmann|first1=Karl|last2=Künnemann|first2=Marvin|pages=79–97|arxiv=1502.01063|isbn=978-1-4673-8191-8|s2cid=1308171}}</ref><ref>{{Cite book|chapter-url=https://doi.org/10.1109/FOCS.2015.14|doi=10.1109/FOCS.2015.14|chapter=Tight Hardness Results for LCS and Other Sequence Similarity Measures|title=2015 IEEE 56th Annual Symposium on Foundations of Computer Science|year=2015|last1=Abboud|first1=Amir|last2=Backurs|first2=Arturs|last3=Williams|first3=Virginia Vassilevska|pages=59–78|isbn=978-1-4673-8191-8|s2cid=16094517}}</ref>

While the dynamic programming algorithm for DTW requires <math>O(NM)</math> space in a naive implementation, the space consumption can be reduced to <math>O(\min(N,M))</math> using [[Hirschberg's algorithm]].