# Asymptotic analysis for machine learning algorithms

I wanted to know if it would practical and useful to analyse machine learning algorithms in terms of asymptotic computational complexity.

I have noticed this is very uncommon. However, I believe it would help us compare these algorithms and decide which one to use for a given scenario.

I am also aware that the running time of most machine learning algorithms is highly dependent on the data. For example, gradient descent algorithm can iterate significantly more times on certain data sets than others.

Considering this, what would be a nice complexity measure for comparing machine learning algorithms?

• pros: indeed they have not been explored! Cons: ML algorithms are probabilistic, which makes them highly unlikely to have a good way to compute accurate enough lower or upper bounds to make those numbers look interesting. Good luck! – Apoorv Feb 10 at 3:34
• @ApoorvIngle I'm afraid both of those statements are simply wrong. First, not all "ML algorithms" are probabilistic. Second, already if you look at the documentation for say scikit-learn (which is a popular Python library), you'll see that the scaling of many algorithms is stated often with references to the literature. – Juho Feb 10 at 15:45
• @Juho My first statement was supposed to mean "ML algorithms can be probabilistic". My second statement still stands correct as it is difficult to compute traditional $\Theta$/$\Omega$ complexity functions for such algorithms. – Apoorv Feb 10 at 18:33
• @ApoorvIngle OK. Even if it's difficult, it doesn't mean that nobody wouldn't have tried. In fact, people succesfully have, meaning it is not true that "... they have not been explored" (see e.g., scikit-learn docs). – Juho Feb 10 at 18:39