Take the 2-minute tour ×

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.

share|improve this question
I think it is nigh impossible to make any sort of guess without hardware specifications and which language/compiler is being used. Are you not able to edit the program to give an idea of how fast it is computing and estimate the time necessary from there? –  Brandon Carter Dec 12 '10 at 0:28
I agree with Brandon, I have voted to close a Not a Real Question. –  Aryabhata Dec 12 '10 at 0:31
I am sorry for the confusion yet all I have is the big-oh for this algorithm and the size of the sound file it has to process. I am just trying to figure out how long would it take for this algorithm to search for a single word with in the sound file that is 1-h long. –  foobar Dec 12 '10 at 0:39
@Sutunc: Perhaps a better question would be, "Are there any benchmarks for some implementation of this?"... –  Aryabhata Dec 12 '10 at 0:40
I sadly dont have any benchmarks of it's implementation. –  foobar Dec 12 '10 at 0:43
show 1 more comment

1 Answer

up vote 0 down vote accepted

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.

share|improve this answer
Thanks that answered my question. –  foobar Dec 12 '10 at 23:37
add comment

Your Answer


