Asymptotic Time Complexity

Asymptotic time complexity gives a high-level understanding of an algorithm's efficiency and scalability, which is crucial for comparing algorithms, predicting their performance, and identifying potential bottlenecks.This short article lists the time complexity for the most common graph, linear algebra and machine learning algorithms.

The most used Big O notation defines the upper bound on the time complexity, so the runtime does not exceed a certain threshold as the size of input grows indefinitely.

Overview

Time complexity (or worst case scenario for the duration of execution given a number of elements) is commonly used in computing science. However, you will be hard pressed to find a comparison of machine learning algorithms using their asymptotic execution time.

Summary

The following summary list the time complexity of some of the most common algorithms used in machine learning including, recursive computation for dynamic programming, linear algebra, optimization and discriminative supervised training.

References

Introduction to Algorithms?T. Cormen, C. Leiserson, R. Rivest - MIT Press 1990

Machine Learning: A probabilistic Perspective?K. Murphy - MIT Press, 2012

Big O cheat sheet

Patrick Nicolas has over 25 years of experience in software and data engineering, architecture design and end-to-end deployment and support with extensive knowledge in machine learning.?He has been director of data engineering at Aideo Technologies since 2017 and he is the?author of "Scala for Machine Learning", Packt Publishing ISBN 978-1-78712-238-3

#machinelearning #graph #timecomplexity #bigonotation #algorithm #performance