Computational Complexity of Machine Learning Algorithms

Pick the right algorithm for your data

Photo by imgix on Unsplash

In this article, we will discuss the computational complexities, both time- and space- complexities, for commonly used machine learning algorithms so that you can make an informed decision on which algorithm to use in production systems based on complexities and prediction accuracy.

Short Intro to Big O:

Time Complexity: Order of time taken for the computation of an algorithm. Represented as a function of parameters associated with the data as well as the algorithm such as volume, number of features, etc., whichever is applicable based on the implementation

Auxiliary Space: It is a temporary space used by the algorithm during the runtime.

Space Complexity: Order of space required during the computation of an algorithm. Represented as a function of parameters associated with the algorithm such as number of features, number of coefficients, number of hidden layers in case of NNs, etc., whichever is applicable based on the algorithm. The space complexity includes both the input data size as well as the auxiliary space used by the algorithm.

Example:

• Mergesort has an auxiliary space of 𝑂(𝑛) and space complexity of 𝑂(𝑛)