A fundamental challenge for running machine learning algorithms onbattery-powered devices is the time and energy limitations, as these deviceshave constraints on resources. There are resource-efficient classifieralgorithms that can run on these devices, but their accuracy is oftensacrificed for resource efficiency. Here, we propose an ultra-low powerclassifier, SEFR, with linear time complexity, both in the training and thetesting phases. SEFR is comparable to state-of-the-art classifiers in terms ofclassification accuracy, but it is 63 times faster and 70 times more energyefficient than the average of state-of-the-art and baseline classifiers onbinary class datasets. The energy and memory consumption of SEFR is veryinsignificant, and it can even perform both train and test phases onmicrocontrollers. To our knowledge, this is the first multipurposeclassification algorithm specifically designed to perform both training andtesting on ultra-low power devices.