Time Complexity of 10 ML Algorithms

This visual depicts the run-time complexity of the 10 most popular ML algorithms.

Why care?

Everyone is a big fan of sklearn implementations.

It takes just two (max three) lines of code to run any ML algorithm with sklearn.

However, due to this simplicity, most people often overlook the core understanding of an algorithm and the data-specific conditions that allow us to use an algorithm.

For instance, you cannot use SVM or t-SNE on a big dataset:

• SVM’s run-time grows cubically with the total number of samples.
• t-SNE’s run-time grows quadratically with the total number of samples.

Another advantage of understanding the run-time is that it helps us understand how an algorithm works end-to-end.

That said, we made a few assumptions in the above table:

• In a random forest, all decision trees may have different depths. We have assumed them to be equal.
  • Then, we find the k-smallest distances from this list.
  • The run-time to determine the k-smallest values may depend on the implementation.
    • Sorting and selecting the k-smallest values will be O(nlogn).
    • But if we use a priority queue, it will take O(nlog(k)).
• In t-SNE, there’s a learning step. However, the major run-time comes from computing the pairwise similarities in the high-dimensional space. You can learn how t-SNE works here: tSNE article.

During inference in kNN, we first find the distance to all data points. This gives a list of distances of size n (total samples).

Today, as an exercise, I would encourage you to derive these run-time complexities yourself.

This activity will give you confidence in algorithmic understanding.

👉 Over to you: Can you tell the inference run-time of KMeans Clustering?

Thanks for reading!