2
$\begingroup$

Currently I am implementing a DTW (Dynamic Time Warping) algorithm for my project. As some will know it has the complexity of O(n^2). Considering a sound file of length 1-h with 44100 sampling. How long will it take to compute it?

(I know we need some other knowledge such as cpu speed, length of the word we are trying to match, our library etc. but you can assume them with your own variables.)

Also, I am aware of the fact that Fast DTW exists and it is way lighter in terms of O complexity but using it is not a case.

  • 0
    @Sutunc: I meant perhaps you can change the question to ask for benchmark results of the algorithm you are interested in! Rather than just asking such a vague question.2010-12-12

1 Answers 1

1

The asymptotic complexity of the algorithm can not provide any information about the time it will take absolutely, but instead shows how running time scales with input size. What I mean is that if you know that it takes $x$ seconds to process $y$ samples of audio, then it will take $4x$ seconds to process $2y$ samples of audio given that the algorithm runs in $O(n^2)$ with $n$ being number of samples.