This site is supported by donations to The OEIS Foundation.
Growth of sequences
From OeisWiki
This is a description of the rates of growth of sequences: bounded, not primitive recursive, and many things inbetween 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
Sequences for which there is an with for all . By definition this includes all sequences with keyword:cons (because these are the digits of a constant, and the digits have a fixed range depending only on the base used), but there are many other examples.
 A000002, A002376, A002828, A080066, A086937, A086965, A086966, A086967, A106276, A106277, A106278, A227781, A227782, A227783, A227784
Conjectured:
Periodic
Sequences for which there is a such that for all (or for all for eventually periodic).
The native denominator in the generating functions of these is , 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 of the denominator polynomial, and this simple recurrence becomes some other product of cyclotomic polynomials in .
Constant
Sequences for which there is a such that for all (or for all for eventually constant).
 Eventually constant: A000007, A035613, A021040, A186684
 Constant: A000004, A000012, A007395, A010701, A010709, A010716, A010722, A010727, A010731, A010734, A010692, A010850, A010851, A010852, A010853, A010854, A010855, A010856, A010857, A010858, A010859, A010860, A010861, A010862, A010863, A010864, A010865, A010866, A010867, A010868, A010869, A010870, A010871
These are in the index to linear recurrences in the order 01, (1) category.
Subpolynomial
Unbounded but subiterated logarithmic
Iterated logarithmic
Sequences for which there are with with if and otherwise.
Superiterated logarithmic but subdoubly logarithmic
Doubly logarithmic
Superdoubly logarithmic but sublogarithmic
Logarithmic
Superlogarithmic but subpolynomial
Polynomial
Sequences with polynomial growth: those for which for some and all large
Sublinear
This includes sequences with n^{α} < a(n) < n^{β} for some 0 < α < β < 1 and large enough n. For example, sequences which grow as Listed below are some sequences with for all and large enough n.
Exponent 1/3
Exponent 1/2
 A000006, A000194, A000267, A000196, A000703, A000934, A001650, A001670, A002024, A003057, A003059, A005145
Exponent phi  1
Exponent 1
These are sequences are sublinear yet grow faster than n^{e} for any e < 1: for all and large enough n.
Linear
Sequences where each called arithmetic sequences. For example: A085959, in which = 37. This includes all firstdegree polynomials, which are found in the index to linear recurrences under order 02, (2,1). It also includes nonpolynomials of linear growth like A212445.
 A000408, A000414, A001690, A002036, A002808, A004169, A004748, A004749, A004750, A004751, A004752, A004753, A004779, A004780, A004781, A005101, A005279
Superlinear but subquadratic
Quadratic
This includes all seconddegree polynomials, which are found in the index to linear recurrences under order 03, (3,3,1). It also includes nonpolynomials of quadratic growth like A181900.
Superquadratic but subcubic
E.g.
Cubic
Supercubic but subquartic
E.g.
Quartic
Subexponential but superpolynomial
Sequences for which for all and all large but for which for all and all large
Exponential
Sequences for which for some and all large
Sequences with rational generating functions with denominator (in lowest terms) which is not a cyclotomic polynomial 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 subdoublyexponential
Sequences for which for all large and
 A000312, A000178, A003266, A050614, A055462, A063439, A113511, A120838, A155877, A161774, A165554, A182856, A217534
Doublyexponential
Sequences for which for some and all large .
 A000278, A000284, A000301, A000371, A002665, A002716, A002813, A002814, A002794, A002795, A006888, A007570, A016088, A039941, A046024, A050548, A052129, A055402, A057194, A064183, A064991, A070177, A087417, A091456, A096580, A100009, A100010, A100011, A100012, A100865, A101361, A103591, A103592, A103593, A103594, A103595, A103596, A103597, A103598, A103599, A103600, A112961, A114953, A114954, A114957, A115410, A116961, A118017, A123180, A125149, A133026, A135378, A142471, A143684, A153450, A159344, A162634, A162647, A171728, A178981, A185981, A210508, A216151
Sequences of the form a(n+1) = a(n)^2 + ...
See the Index page.
 A000058, A000289, A000324, A001042, A001146, A001510, A001543, A001544, A001566, A001696, A001697, A001699, A001999, A002065, A003010, A003095, A003096, A003423, A003487, A004019, A005267, A013589, A014253, A028300, A051179, A056207, A000215, A000283, A007018, A058181, A058182, A062000, A063573, A065035, A067686, A076725, A086851, A092500, A092501, A098152, A099941, A099729, A100523, A100528, A110360, A110368, A110383, A113848, A115590, A117805, A118623, A123180, A125046, A126023, A129871, A135927, A143760, A143761, A143762, A143763, A143764, A143765, A143766, A153059, A153060, A153061, A153062, A174864, A186750, A204321, A228931
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 superdoublyexponential
Sequences for which for all and all large but for which for some , where is the times iterated exponential. Informally, these are towers with fixed height.
Nonelementary, but subtetrational
Sequences for which for which for all and large but for which for all large
No sequences in the OEIS are known to have this behavior, but see Chazelle 2009^{[1]} for an example of a sequence with behavior
Iterated exponential and superiterated exponential
Tetrational
Sequences for which for some and all large . Informally, gives the height of the exponential tower.
Examples include:
Primitive recursive, but supertetrational
Sequences for which for all and all large but for which there is a with for some
Not primitive recursive
Sequences for which for all and large enough
Examples include:
See also
Notes
 ↑ Bernard Chazelle, The convergence of bird flocking (2009). Preliminary version presented at the 26th Annual Symposium on Computational Geometry, 2010.
External links
 Mohammad R. Salavatipour, Lecture 5: Growth of Functions, CMPUT 204: Algorithms I, Department of Computing Science, University of Alberta.
Cite this page as
Charles R Greathouse IV, Growth of sequences.— From the OnLine Encyclopedia of Integer Sequences® Wiki (OEIS® Wiki). [https://oeis.org/wiki/Growth_of_sequences]