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.

  • 2
    $\begingroup$ 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? $\endgroup$
    – bzc
    Dec 12, 2010 at 0:28
  • $\begingroup$ I agree with Brandon, I have voted to close a Not a Real Question. $\endgroup$
    – Aryabhata
    Dec 12, 2010 at 0:31
  • $\begingroup$ 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. $\endgroup$
    – foobar
    Dec 12, 2010 at 0:39
  • $\begingroup$ @Sutunc: Perhaps a better question would be, "Are there any benchmarks for some implementation of this?"... $\endgroup$
    – Aryabhata
    Dec 12, 2010 at 0:40
  • $\begingroup$ I sadly dont have any benchmarks of it's implementation. $\endgroup$
    – foobar
    Dec 12, 2010 at 0:43

1 Answer 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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .