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?