Quadratic Growth - Examples

Examples

Examples of quadratic growth include:

• Any quadratic polynomial.
• Certain integer sequences such as the triangular numbers. The nth triangular number has value n(n+1)/2, approximately n2/2.

For a real function of a real variable, quadratic growth is equivalent to the second derivative being constant (i.e., the third derivative being zero), and thus functions with quadratic growth are exactly the quadratic polynomials, as these are the kernel of the third derivative operator Similarly, for a sequence (a real function of an integer or natural number variable), quadratic growth is equivalent to the second finite difference being constant (the third finite difference being zero), and thus a sequence with quadratic growth is also a quadratic polynomial. Indeed, an integer-valued sequence with quadratic growth is a polynomial in the zeroth, first, and second binomial coefficient with integer values. The coefficients can be determined by taking the Taylor polynomial (if continuous) or Newton polynomial (if discrete).

Algorithmic examples include:

• The amount of time taken in the worst case by certain algorithms, such as insertion sort, as a function of the input length.
• The numbers of live cells in space-filling cellular automaton patterns such as the Breeder (CA), as a function of the number of time steps for which the pattern is simulated.
• Metcalfe's law stating that the value of a communications network grows quadratically as a function of its number of users