Proofs of Algorithm Correctness and Runtime Estimates · Polynomial, Exponential, and Logarithmic Functions
Lesson 1
One of the goals of this section is to see how to estimate the growth rate of functions. In discrete mathematics, such estimates are very often needed—for example, in algorithms, combinatorics, cryptography, coding theory. We start by recalling how the three most commonly encountered functions behave—logarithmic, polynomial, and exponential.