This site is supported by donations to The OEIS Foundation.

Growth of sequences

From OeisWiki

Jump to: navigation, search

This is a description of the rates of growth of sequences: bounded, not primitive recursive, and many things in-between like iterated logarithmic, tetrational, and polynomial. Note that not all sequences are included—sequences like A124625 with alternating growth do not fall into the classification below.

Contents

Bounded

\scriptstyle a(n) \,\in\, O \left( 1 \right).

Sequences for which there is an \scriptstyle N with \scriptstyle -N \,\le\, a(n) \,\le\, N for all \scriptstyle n. By definition this includes all sequences with keyword:cons, but there are many other examples.

Conjectured:

Periodic

Sequences for which there is a \scriptstyle k such that \scriptstyle a(n) \,=\, a(n+k) for all \scriptstyle n (or for all \scriptstyle n \,>\, N for eventually periodic).

The native denominator in the generating functions of these is \scriptstyle 1 - x^k, which makes them traceable through the index to linear recurrences. If 1 is also a root of the numerator of the generating function, this may lower the degree \scriptstyle k of the denominator polynomial, and this simple recurrence becomes some other product of cyclotomic polynomials in \scriptstyle x.

Constant

Sequences for which there is a \scriptstyle k such that \scriptstyle a(n) \,=\, k for all \scriptstyle n (or for all \scriptstyle n \,>\, N for eventually constant).

These are in the index to linear recurrences in the order 01, (1) category.

Subpolynomial

Unbounded but sub-iterated logarithmic

Iterated logarithmic

Sequences for which there are \scriptstyle 0 \,<\, \alpha \,<\, \beta \, with \scriptstyle \alpha \, \log^*(n) \,\le\, a(n) \,\le\, \beta \, \log^*(n) \, with \scriptstyle \log^*(x) \,=\, 0 \, if \scriptstyle x \,\le\, 0 \, and \scriptstyle \log^*(x) \,=\, \log^*(\log x) + 1 \, otherwise.

Super-iterated logarithmic but sub-doubly logarithmic

Doubly logarithmic

Super-doubly logarithmic but sublogarithmic

Logarithmic

Superlogarithmic but subpolynomial

Polynomial

a(n)\in \bigcup_{k}O(n^k)\cap\bigcup_{k>0}\Omega(n^k)

Sequences with polynomial growth: those for which \scriptstyle n^\alpha \,\le\, a(n) \,\le\, n^\beta \, for some \scriptstyle 0 \,<\, \alpha \,<\, \beta \, and all large \scriptstyle n. \,

Sublinear

This includes sequences with nα < a(n) < nβ for some 0 < α < β < 1 and large enough n. For example, sequences which grow as \Theta(\sqrt n).

Linear

\scriptstyle a(n) \,\in\, O \left( n \right). \,

Sequences where each \scriptstyle a(n) \,=\, a(n - 1) + c, \, called arithmetic sequences. For example: A085959, in which \scriptstyle c \, = 37. This includes all first-degree polynomials, which are found in the index to linear recurrences under order 02, (-2,1). It also includes non-polynomials of linear growth like A212445.

Superlinear but subquadratic

a(n) \in \omega\left(n\right) \cap o \left( n^2 \right)

Quadratic

\scriptstyle a(n) \,\in\, O \left( n^2 \right). \,

This includes all second-degree polynomials, which are found in the index to linear recurrences under order 03, (3,-3,1). It also includes non-polynomials of quadratic growth like A181900.

Superquadratic but subcubic

\scriptstyle a(n) \,\in\, O \left( n^k \right),\, 2 \,<\, k \,<\, 3. \,

E.g. \scriptstyle a(n) \,\in\, O \left( n^2 \log n \right) \,\subset\, O \left( n^{2 + \epsilon} \right). \,

Cubic

\scriptstyle a(n) \,\in\, O \left( n^3 \right). \,

Supercubic but subquartic

\scriptstyle a(n) \,\in\, O \left( n^k \right),\, 3 \,<\, k \,<\, 4. \,

E.g. \scriptstyle a(n) \,\in\, O \left( n^3 \log n \right) \,\in\, O \left( n^{3 + \epsilon} \right). \,

Quartic

\scriptstyle a(n) \,\in\, O \left( n^4 \right). \,

Sub-exponential but superpolynomial

Sequences for which \scriptstyle n^\alpha \,<\, a(n) \, for all \scriptstyle \alpha \, and all large \scriptstyle n(\alpha), \, but for which \scriptstyle a(n) \,<\, \alpha^n \, for all \scriptstyle \alpha \,>\, 1 \, and all large \scriptstyle n(\alpha). \,

Exponential

Sequences for which \scriptstyle \alpha^n \le a(n) \le \beta^n for some \scriptstyle 1 < \alpha \le \beta and all large \scriptstyle n.

Sequences with rational generating functions with denominator (in lowest terms) which is not a power of \scriptstyle x-1 have exponential growth. Equivalently, linear recurrence relations in which one of the roots of the characteristic polynomial has absolute value greater than 1.

Minimally superincreasing sequences have exponential growth (though some superincreasing sequences have superexponential growth).

Superexponential

Superexponential but sub-doubly-exponential

Sequences for which \scriptstyle \alpha^n \,<\, a(n) \,<\, \alpha \,\uparrow^2\, n \, for all large \scriptstyle \alpha \, and \scriptstyle n(\alpha). \,

Doubly-exponential

Sequences for which \scriptstyle \exp{\left( \alpha^n \right)} \,\le\, a(n) \,\le\, \exp{\left( \beta^n \right)} \, for some \scriptstyle 1 \,<\, \alpha \,\le\, \beta \, and all large \scriptstyle n \,.

Sequences of the form a(n+1) = a(n)^2 + ...

See the Index page.

These are questionable members: a strict definition would not admit them but some might. For example, the last term may be not just squared but multiplied by a constant.

Conjectural

Elementary, but super-doubly-exponential

Sequences for which \scriptstyle \exp{\left( \alpha^n \right)} \,<\, a(n) \, for all \scriptstyle \alpha \, and all large \scriptstyle n(\alpha), \, but for which \scriptstyle a(n) \,<\, \exp_k{\left( \alpha^n \right)} \, for some \scriptstyle k \,, where \scriptstyle \exp_k \, is the \scriptstyle k \,-times iterated exponential. Informally, these are towers with fixed height.

Nonelementary, but sub-tetrational

Sequences for which for which \scriptstyle \exp_k{\left( \alpha^n \right)} \,<\, a(n) \, for all \scriptstyle k \, and large \scriptstyle n(k), \, but for which \scriptstyle a(n) \,<\, \alpha \,\uparrow^2\, n \, for all large \scriptstyle n(\alpha).\,

No sequences in the OEIS are known to have this behavior, but see Chazelle 2009[1] for an example of a sequence with behavior \scriptstyle 2 \,\uparrow^2\, \Theta(\log n). \,

Iterated exponential and super-iterated exponential

Tetrational

Sequences for which \scriptstyle \alpha \,\uparrow^2\, n \,\le\, a(n) \,\le\, \beta \,\uparrow^2\, n \, for some \scriptstyle e^{1/e} \,<\, \alpha \,\le\, \beta \, and all large \scriptstyle n \,. Informally, \scriptstyle n \, gives the height of the exponential tower.

Examples include:

Primitive recursive, but super-tetrational

Sequences for which \scriptstyle \alpha \,\uparrow^2\, n \,<\, a(n) \, for all \scriptstyle \alpha \, and all large \scriptstyle n(\alpha), \, but for which there is a \scriptstyle k \, with \scriptstyle a(n) \,\le\, \alpha \,\uparrow^k\, \, for some \scriptstyle \alpha \,>\, e^{1/e}. \,

Not primitive recursive

Sequences for which \scriptstyle 2 \,\uparrow^k\, n \,<\, a(n) \, for all \scriptstyle k \, and large enough \scriptstyle n(k). \,

Examples include:

See also

Notes

  1. Bernard Chazelle, The convergence of bird flocking (2009). Preliminary version presented at the 26th Annual Symposium on Computational Geometry, 2010.

External links


Cite this page as

Charles R Greathouse IV, Growth of sequences. — From the On-Line Encyclopedia of Integer Sequences® (OEIS®) wiki. (Available at https://oeis.org/wiki/Growth_of_sequences)

Personal tools