I read on a book that in general k-NN (no optimizations), given

  • $d$ dimensions
  • $n$ examples

every computation of distance is $O(d)$. Since every example has to be compared with all the other ones, the complexity is $O(dn^2)$

I am doing 1-Nearest-Neighbors with Dynamic Time Warping as distance "metric".

The complexity to my calculations, was, given:

  • $d$ dimensions
  • $n$ examples
  • $m$ instances of feature for each example
  • (bonus) $c$ classes

$O(m^2)$ complexity of a single comparison of DTW algorithm

$O(d\,n^2)$ complexity of general k-NN

Thus in a single training/test, the complexity for all the computation is:


If I have $c$ classes, and $c$ classifiers, one for each class, with each having custom features, the overall complexity is


Is this correct? Or I'm missing something?

EDIT: An example contains temporal data which gives out another dimension. You can imagine an example as a matrix where $d$ is the number of features (columns), and $m$ the number of instances of features (rows).

So I can have a table like this

<$m$> | $f_1$ | $f_2$ | $f_3$ | ...

$m_1$ | $a$ | $b$ | $c$ | ...

$m_2$ | $a'$ | $b'$ | $c'$ | ...

When I compare for a single feature two examples, the DTW distance is a scalar value for each feature, so the comparison becomes

$dist_1$ | $dist_2$ | $dist_3$ | ...

with $dist_i$ scalar $\forall i$ and $|\{dist_i | \forall i\}| = d$

The time complexity to calculate each $dist_i$ is $O(m^2)$ (DTW algorithm has quadratic complexity, or $m\cdot m'$ if different number of lengths).

  • 2
    $\begingroup$ I don't understand your setup. What is meant by a dimension vs a feature? Normally you work with a feature vector, so the number of dimensions is equal to the number of features, i.e., $d=m$, so I'm not sure why you have different variables for those. Can you edit your question to clarify? $\endgroup$
    – D.W.
    Apr 16 '19 at 20:18
  • $\begingroup$ Sure. $m$ are not the features, are the instances of feature in an example. Let's say I have this example: f1 | f2 | f3 | ...\\ [$m1$] a | b | c\\ [$m2$] a' | b' | c'\\ [$m3$] a'' | b'' | c'' Each example has this structure. $d$ is the number of $f1, f2, f3, ...$. $m$ is the number of the rows in the table. The table here is not the dataset but just an example, so an esample can be imagined as a tensor. $\endgroup$ Apr 16 '19 at 21:36
  • $\begingroup$ I edited the question, hope it's more clear $\endgroup$ Apr 16 '19 at 21:43
  • $\begingroup$ The dataset can be imagined as a tensor* in the comment before $\endgroup$ Apr 16 '19 at 22:36

The running time of a nearest neighbor classifier is the time to compute the distance between two examples, multiplied by the number of pairs of examples you need to compute the distance between. So, all you need to do is figure out each of those two numbers.

For ordinary k-nn, it takes $O(d)$ time to compute the distance between two $d$-dimensional examples, and to classify an example, you need to compare it to all other examples, i.e., $n$ pairs. So, the running time to classify a single point with ordinary k-nn is $O(dn)$ (not $O(dn^2)$ as you wrote).

For your scheme, it appears it takes $O(dm^2)$ time to compute the distance between two examples (you need to run the DTW algorithm $d$ times, and running DTW once takes $O(m^2)$ time). The number of pairs doesn't change; to classify a single example, you still compute the distance to each example in the training set, so $n$ distance computations. Therefore, the running time to classify a single point in your scheme is $O(dm^2n)$ (not $O(dm^2n^2)$ as you wrote).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.