Machine learning is a popular method of learning functions from data to represent and to classify sensor inputs, multimedia, emails, and calendar events. Smartphone applications have been integrating more and more intelligence in the form of machine learning. Machine learning functionality now appears on most smartphones as voice recognition, spell checking, word disambiguation, face recognition, translation, spatial reasoning, and even natural language summarization. Excited app developers who want to use machine learning on mobile devices face one serious constraint that they did not face on desktop computers or cloud virtual machines: the end-user’s mobile device has limited battery life, thus computationally intensive tasks can harm end users’ phone availability by draining batteries of their stored energy. Currently, there are few guidelines for developers who want to employ machine learning on mobile devices yet are concerned about software energy consumption of their applications. In this paper, we combine empirical measurements of different machine learning algorithm implementations with complexity theory to provide concrete and theoretically grounded recommendations to developers who want to employ machine learning on smartphones. We conclude that some implementations of algorithms, such as J48, MLP, and SMO, do generally perform better than others in terms of energy consumption and accuracy, and that energy consumption is well-correlated to algorithmic complexity. However, to achieve optimal results a developer must consider their specific application as many factors — dataset size, number of data attributes, whether the model will require updating, etc. — affect which machine learning algorithm and implementation will provide the best results.