Analysis of Algorithms

Analysis of algorithms is the formal study of how much time and memory an algorithm needs as a function of the size of its input, used to compare different methods for solving the same problem before either is built. Donald Knuth developed the field's rigorous mathematical treatment across The Art of Computer Programming, the multi-volume work he began in 1962 and whose first volume appeared in 1968, working out exact and asymptotic running-time formulas for the sorting, searching and combinatorial algorithms he surveyed. In a 1976 note, Big Omicron and Big Omega and Big Theta, he set out precise definitions for the asymptotic notations that describe an algorithm's growth in the best, worst and typical case, including Big O notation, fixing the meaning computer science has used for it since. This treatment gave later work on computational complexity, the classification of problems by how the resources an algorithm needs grow with the size of its input, a shared, rigorous vocabulary to build on, though the field of computational complexity itself was founded separately.