mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

, a function or

sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is cal ...

is said to exhibit quadratic growth when its values are proportional to the

square In geometry, a square is a regular polygon, regular quadrilateral. It has four straight sides of equal length and four equal angles. Squares are special cases of rectangles, which have four equal angles, and of rhombuses, which have four equal si ...

of the function argument or sequence position. "Quadratic growth" often means more generally "quadratic growth in the limit", as the argument or sequence position goes to infinity – in big Theta notation,

f(x)=\Theta(x^2)

. This can be defined both continuously (for a real-valued function of a real variable) or discretely (for a sequence of real numbers, i.e., real-valued function of an

integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...

natural number In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...

variable).

Examples

Examples of quadratic growth include: *Any

quadratic polynomial In mathematics, a quadratic function of a single variable is a function of the form :f(x)=ax^2+bx+c,\quad a \ne 0, where is its variable, and , , and are coefficients. The expression , especially when treated as an object in itself rather tha ...

. *Certain

integer sequence In mathematics, an integer sequence is a sequence (i.e., an ordered list) of integers. An integer sequence may be specified ''explicitly'' by giving a formula for its ''n''th term, or ''implicitly'' by giving a relationship between its terms. For ...

s such as the

triangular number A triangular number or triangle number counts objects arranged in an equilateral triangle. Triangular numbers are a type of figurate number, other examples being square numbers and cube numbers. The th triangular number is the number of dots in ...

s. The

n

th triangular number has value

n(n+1)/2

, approximately

n^2/2

. For a real function of a real variable, quadratic growth is equivalent to the

second derivative In calculus, the second derivative, or the second-order derivative, of a function is the derivative of the derivative of . Informally, the second derivative can be phrased as "the rate of change of the rate of change"; for example, the secon ...

being constant (i.e., the

third derivative In calculus, a branch of mathematics, the third derivative or third-order derivative is the rate at which the second derivative, or the rate of change of the rate of change, is changing. The third derivative of a function y = f(x) can be denot ...

being zero), and thus functions with quadratic growth are exactly the quadratic polynomials, as these are the kernel of the third derivative operator

D^3

. Similarly, for a sequence (a real function of an integer or natural number variable), quadratic growth is equivalent to the second

finite difference A finite difference is a mathematical expression of the form . Finite differences (or the associated difference quotients) are often used as approximations of derivatives, such as in numerical differentiation. The difference operator, commonly d ...

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 In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the t ...

with integer values. The coefficients can be determined by taking the Taylor polynomial (if continuous) or

Newton polynomial In the mathematical field of numerical analysis, a Newton polynomial, named after its inventor Isaac Newton, is an interpolation polynomial for a given set of data points. The Newton polynomial is sometimes called Newton's divided differences inter ...

(if discrete). Algorithmic examples include: *The amount of time taken in the worst case by certain

algorithm In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...

s, such as

insertion sort Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time by comparisons. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. Howev ...

, as a function of the input length. *The numbers of live cells in space-filling

cellular automaton A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessel ...

patterns such as the

breeder A breeder is a person who selectively breeds carefully selected mates, normally of the same breed, to sexually reproduce offspring with specific, consistently replicable qualities and characteristics. This might be as a farmer, agriculturalist ...

, as a function of the number of time steps for which the pattern is simulated. *

Metcalfe's law Metcalfe's law states that the financial value or influence of a telecommunications network is proportional to the square of the number of connected users of the system (2). The law is named after Robert Metcalfe and was first proposed in 1980 ...

stating that the value of a communications network grows quadratically as a function of its number of users..

References

Asymptotic analysis {{Mathanalysis-stub

Examples

See also

References