Is this computational complexity of the k-NN (custom distance) correct?

Question

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:

$O(d\,n^2\,m^2)$

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

$O(c\,d\,n^2\,m^2)$

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).

Answer 1

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).