Runtime complexity of DSM
To analyze the DSM prototype generation algorithm with regard to its runtime complexity, two phases can be distinguished, namely initialization and actual reduction. The phases will be analyzed on their worst-case runtime.The following conventions are made: The results of this analysis are shown in Table Summarizing Table It has to be noted that the time complexity in reduction can principally be reduced from Generally speaking, if Due to the fact that the number of prototypes Interestingly, this would mean that DSM has the same runtime complexity in reduction (which is only performed once) as standard kNN in each single prediction step (or even better if a higher number of 