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

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

• 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?
– D.W.
Apr 16, 2019 at 20:18
• 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. Apr 16, 2019 at 21:36
• I edited the question, hope it's more clear Apr 16, 2019 at 21:43
• The dataset can be imagined as a tensor* in the comment before Apr 16, 2019 at 22:36

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