Growth of sequences

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.

Bounded

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

Sequences for which there is an $\scriptstyle N$ with $\scriptstyle -N\,\leq \,a(n)\,\leq \,N$ for all $\scriptstyle n$ . 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, A008683, A039702, A039703, A039704, A039705, A039706, A051034, A073058, A080066, A084301, A086937, A086965
Base: A000030, A000455, A001073, A001191, A001355, A002993, A002994, A003076, A003893, A004426, A004427, A004428, A004429, A004430, A007376, A007652, A008564, A008565, A008566, A008567, A008568, A008569, A008570, A008571, A008572, A008573, A008905, A008952, A008960, A008963, A023961, A030132, A030588, A030604, A031007, A031045, A031253, A031269, A031312, A031347, A033988, A033989, A038194, A054054, A054055
A086966, A086967, A091664, A095048, A104608, A104609, A104610, A104611, A104612, A104613, A104614, A104615, A104616, A104617, A104618, A104619, A105198, A106276, A106277, A106278, A133613, A133614, A133615, A133616, A133617, A133618, A133619, A136690, A136691, A136692, A136693, A136694, A136695, A136696, A136697, A136698, A136699, A136700, A136701, A136702, A144539, A144540, A144541, A144542, A144543, A144544, A158799, A215732, A225224, A227781, A227782, A227783, A227784, A266798, A269591, A269592, A290566, A359141

Conjectured:

A031346, A180021

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

A000035, A010873, A010874, A010875, A010876, A010877, A010878, A010879, A010880, A010881, A010882, A010883, A010884, A010885, A010886, A010887 A010875, A038605, A131027, A133880, A165472, A175723, A203571, A242627

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

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 sub-iterated logarithmic

A098820

Iterated logarithmic

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

A010096, A001069

Super-iterated logarithmic but sub-doubly logarithmic

A334789

Doubly logarithmic

A063510

Super-doubly logarithmic but sublogarithmic

A099563 (inverse gamma growth, ~ log n/log log n)

Logarithmic

A000193, A000195, A000523, A003434, A004233, A029837, A038605, A055778, A063511, A070939, A070941, A084320, A102572, A133775, A190796

Superlogarithmic but subpolynomial

A010553 (exp(sqrt(log n)) or so)

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 }\,\leq \,a(n)\,\leq \,n^{\beta }\,$ for some $\scriptstyle 0\,<\,\alpha \,<\,\beta \,$ and all large $\scriptstyle n.\,$

Sublinear

This includes sequences with $n^{\alpha }<a(n)<n^{\beta }$ for some $0<\alpha <\beta <1$ and large enough n. For example, sequences which grow as $\Theta ({\sqrt {n}}).$ Listed below are some sequences with $n^{\alpha -\varepsilon }<a(n)<n^{\alpha +\varepsilon }$ for all $\varepsilon >0$ and large enough n.

Exponent 1

These are sequences are sublinear yet grow faster than $n^{e}$ for any $e<1$ : $n^{1-\varepsilon }<a(n)<kn$ for all $k,\varepsilon >0$ and large enough n.

A002410, A002505, A008508

Linear

\scriptstyle a(n)\asymp n.

Sequences where each $\scriptstyle a(n)\,=\,a(n-1)+c,\,$ are 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.

A strictly increasing sequence has linear growth if and only if its lower density is positive.

All Beatty sequences have linear growth (by definition).

Beatty sequences: A001950, A003622†, A022844
0 < lower density < 1: A000069, A000408, A000452, A001477, A001633, A001637, A001969, A002035, A003052, A003159, A003657, A004709, A005100, A005101, A005114, A005117, A005408, A005835, A005843, A006037, A006285, A007310, A007775, A008365, A008366, A008585, A008905, A010061, A014847, A016777, A016813, A016825, A022342, A023196, A026179, A026225, A030059, A030229, A034683, A047303, A063743, A068782, A078923, A103288, A275616, A016789, A004767, A008586, A008574, A016921, A008588, A008587, A016945, A080653, A007378, A080637, A079905, A336175, A058986, A336909
Lower density not known to be 1 or smaller than 1, but known positive: A005279
Density 1: A000027, A000414, A000977, A001690, A002036, A002808, A004169, A004748, A004749, A004750, A004751, A004752, A004753, A004779, A004780, A004781, A007369, A007617, A011539, A183217, A028310*
A035336, A035337, A036785, A038109, A038838, A039955, A039957, A045520, A045521, A045522, A045523, A045524, A045525, A045526, A045527, A045528, A045572, A046099, A046101, A046642, A048107, A048109, A049511, A049532, A053224, A053226, A053738, A053754, A054979, A055041, A055047, A056913, A059269, A062289, A064736, A065502, A066498, A066500, A066502, A067259, A067497, A068140, A068403, A068404, A068781, A069059, A072587, A080147, A080148, A081706, A082293, A087248, A088725, A091177, A091178, A092433, A104210, A121707, A121943, A122132, A125134, A129575, A131835, A132141, A133466, A134334, A134860, A143028, A143029, A143030, A143031, A143032, A143033, A143034, A143035, A143036, A145204, A160591, A162643, A162644, A171102, A176995, A187238, A187398, A187516, A190641, A195086, A195087, A197680, A209061, A217394, A217395, A217397, A217398, A217399, A217400, A217401, A217402, A228082, A229300, A229301, A229302, A229303, A229304, A229305, A229306, A229307, A229829, A232705, A232744, A232745, A248150, A252895, A276078, A307958, A308053, A318720, A320628, A320629, A321147, A323024, A325128, A325130, A325424, A326835, A333634, A336064, A336066, A336068, A338539, A338540, A338541, A338542, A340152, A342050, A342051, A358350

Conjectured: A005279, A096399, A319630, A325160, A194186, A003147**, A127666, A129485, A070087, A070089, A293186, A112643, A348274, A194184, A348604

* Not a set

† Linear shift of a Beatty sequence

** Proved on the assumption of GRH.

Superlinear but subquadratic

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

A000093, A005836

Quasilinear

n\ll a(n)\ll n^{1+\varepsilon }{\text{ for all }}\varepsilon >0

A000040, A005153, A174973, A216761, A216762, A221284, A361300

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:

A001597, A045619, A100613, 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).\,$

A221285

Cubic

a(n)\asymp n^{3}.

A065733, A360284

Supercubic but subquartic

a(n)=o(n^{4}){\text{ but }}\lim _{n\to \infty }a(n)/n^{3}=\infty .

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

Quartic

a(n)\asymp n^{4}.

A124162, A358212

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 ).\,$

A058577, A061567

Exponential

Sequences for which $\scriptstyle \alpha ^{n}\leq a(n)\leq \beta ^{n}$ for some $\scriptstyle 1<\alpha \leq \beta$ and all large $\scriptstyle n.$

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

Sequences are sorted by base, when possible. Ranges can represent either uncertainty about the value of the base, $\scriptstyle \alpha <\beta$ , or uncertainty about which of these cases hold. See the individual sequence entries for more details.

1.1184... to 2: A160675
1.3017597 to 1.3017619: A006156
2: A002804, A215422
phi^2 = phi + 1 = 2.61803...: A065885, A007598
e = 2.718...: A002387, A034386
6: A342452
e^3 = 20.08...: A091463

Superexponential

Superexponential but sub-doubly-exponential

Sequences for which $\scriptstyle \alpha ^{n}<a(n)$ for all $\scriptstyle \alpha >1$ and sufficiently large $\scriptstyle n(\alpha ),$ but $\scriptstyle a(n)<\alpha \uparrow ^{2}n$ for all $\scriptstyle \alpha >e^{1/e}$ and sufficiently large $\scriptstyle n(\alpha ).$

A000312, A000178, A002109, A003266, A050614, A055462, A063439, A113511, A120838, A155877, A161774, A165554, A182856, A200564, A217534, A296653

Doubly-exponential

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

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, A110368, A112961, A114953, A114954, A114957, A115410, A116961, A118017, A123180, A125149, A133026, A135378, A142471, A143684, A153450, A159344, A162634, A162647, A171728, A178981, A185981, A210508, A216151, A333554, A348456

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

A001054, A001056, A001601, A001064, A002812, A007660, A114793, A114950, A172028

Conjectural

A037096, A037097, A136386

Elementary, but super-doubly-exponential

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

A116213, A002488, A058124, A171874, A171879, A195529, A358972

Nonelementary, but sub-tetrational

Sequences for which for which $\scriptstyle \exp _{k}{\left(\alpha ^{n}\right)}<a(n)$ for all k and large $\scriptstyle n(k),\,$ but for which $\scriptstyle a(n)<\alpha \uparrow ^{2}n$ for all $\scriptstyle \alpha >e^{1/e}$ and sufficiently 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\,\leq \,a(n)\,\leq \,\beta \,\uparrow ^{2}\,n\,$ for some $\scriptstyle e^{1/e}\,<\,\alpha \,\leq \,\beta \,$ and all large $\scriptstyle n\,$ . Informally, $\scriptstyle n\,$ gives the height of the exponential tower.

Examples include:

A006050, A045646, A014221, A073236, A115658, A173566

These are questionable members: a strict definition would not admit them but some might. For example, they might be comparable to a tetrational function with a non-constant base.

A091409 (conjectured)

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)\,\leq \,\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).\,$