A growth function shows the relationship between the size of the problem and
the value to be optimized.
When studying the complexity of an algorithm, we are concerned with the growth
in the number of operations required by the algorithm as the size of the problem
increases. In order to get a handle on its complexity, we first look for a function that
gives the number of operations in terms of the size of the problem, usually measured
by a positive integer n, to which the algorithm is applied. We then try to compare
values of this function, for large n, to the values of some known function, such as
a power function, exponential function, or logarithm function. Thus, the growth of
functions refers to the relative size of the values of two functions for large values of the
independent variable. This is one of the main areas in this course in which experience
with the concept of a limit from calculus will be of great help.
Quote: