A growth rate describes how a quantity changes as its input grows. For algorithms, the quantity is usually running time or memory, and the input size is written as n. section 4.7
Big-O notation groups functions by how quickly they grow. Saying f(n) = O(n) means f grows like a straight line, within suitable upper and lower bounds for sufficiently large inputs. section 4.7
Common growth classes range from gentle to explosive:
- O(1) stays constant as the input grows. section 4.8
- Logarithmic growth is very slow; linear growth increases at a steady rate. section 4.8
- Linearithmic growth, such as O(n * log(n)), accelerates moderately and suits large sorting jobs. section 4.8
- Polynomial growth accelerates rapidly, while exponential growth can become unmanageable even for moderately sized inputs. section 4.8
Choosing a sorting algorithm
Sorting one billion elements with a linearithmic algorithm such as mergesort or heapsort is estimated in minutes, while quadratic selection sort could take thousands of years under the same model. section 4.9
Some of the growth rates you might encounter when studying algorithms. From left to right, the functions grow increasingly faster.
Use the growth-rate graph to compare how slowly or quickly common function classes increase as inputs become larger. section 4.8
