mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

, a

function Function or functionality may refer to: Computing * Function key, a type of key on computer keyboards * Function model, a structured representation of processes in a system * Function object or functor or functionoid, a concept of object-oriente ...

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 calle ...

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

square In Euclidean geometry, a square is a regular quadrilateral, which means that it has four equal sides and four equal angles (90-degree angles, π/2 radian angles, or right angles). It can also be defined as a rectangle with two equal-length adj ...

of the function argument or sequence position. "Quadratic growth" often means more generally "quadratic growth in the

limit Limit or Limits may refer to: Arts and media * ''Limit'' (manga), a manga by Keiko Suenobu * ''Limit'' (film), a South Korean film * Limit (music), a way to characterize harmony * "Limit" (song), a 2016 single by Luna Sea * "Limits", a 2019 ...

", 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 Real may refer to: Currencies * Brazilian real (R$) * Central American Republic real * Mexican real * Portuguese real * Spanish real * Spanish colonial real Music Albums * ''Real'' (L'Arc-en-Ciel album) (2000) * ''Real'' (Bright album) (2010) ...

-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 (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...

natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''Cardinal n ...

variable).

Examples

Examples of quadratic growth include: *Any

quadratic polynomial In mathematics, a quadratic polynomial is a polynomial of degree two in one or more variables. A quadratic function is the polynomial function defined by a quadratic polynomial. Before 20th century, the distinction was unclear between a polynomia ...

. *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 . Roughly speaking, the second derivative measures how the rate of change of a quantity is itself changing; for example, ...

being constant (i.e., the

third derivative In calculus, a branch of mathematics, the third 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 denoted by :\frac,\quad f(x),\qua ...

being zero), and thus functions with quadratic growth are exactly the quadratic polynomials, as these are the

kernel Kernel may refer to: Computing * Kernel (operating system), the central component of most operating systems * Kernel (image processing), a matrix used for image convolution * Compute kernel, in GPGPU programming * Kernel method, in machine learnin ...

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 . If a finite difference is divided by , one gets a difference quotient. The approximation of derivatives by finite differences plays a central role in finite difference methods for t ...

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 In mathematics, the Taylor series or Taylor expansion of a function is an infinite sum of terms that are expressed in terms of the function's derivatives at a single point. For most common functions, the function and the sum of its Taylor ser ...

(if continuous) or

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

(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 rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...

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 value of a telecommunications network is proportional to the square of the number of connected users of the system (''n''2). First formulated in this form by George Gilder in 1993, and attributed to Robert Metcalf ...

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