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