Asymptotic analysis for machine learning algorithms
Well, first let's clarify the following. Asymptotic Complexity and real life situations are different. Please take a look at this Question.

Now, machine learning is a very hard topic to explore precisely the asymptotic complexity of your algorithms. If we think machine learning as linear algebra, then the asymptotic complexity is the complexity of multiplying matrices. In the area of machine learning, the most important thing is not so much the complexity, but the efficient use of GPUs and TPUs. Let's say you need to train a model for Natural Language Understanding and you use LSTM, GRU and CNN (CNN ?!). Each algorithm has its own complexity because each one does easier or harder calculations. Unfortunately there is no metric such as Model's Accuracy / # of computations. But we all can agree that two LSTM can vastly vary on their speed depending on how good use of GPUs and TPUs they make.