A logarithmic function grows very slowly as its input increases. In algorithm analysis, this makes logarithmic growth an important benchmark for judging how running time scales with larger inputs. section 4.8 section 4.9
Compare logarithmic growth with other common growth rates:
- Linear functions grow at a constant rate. section 4.8
- Linearithmic functions grow faster than logarithmic functions but remain slower than polynomial functions. section 4.8
- Polynomial functions accelerate rapidly, while exponential functions grow extremely fast as input size increases. section 4.8
- Asymptotic formulas estimate an algorithm’s order of magnitude rather than its exact execution time. 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 figure to compare how logarithmic, linear, linearithmic, polynomial, and exponential functions increase. section 4.8
How long does it take to run an algorithm? That depends on the order of growth of its running time. All results are approximated.
Use the runtime figure to connect orders of growth with approximate execution times for algorithms operating on arrays. section 4.9
