[seqfan] Re: Heuristic growth rate

Andrew N W Hone A.N.W.Hone at kent.ac.uk
Tue May 7 07:33:17 CEST 2019

Hi Vladimir, 

If the growth of x_n is polynomial in n, then plot log x_n versus log n and the asymptotic slope gives the leading 
exponent k, 

x_n ~ C n^k , 

and the y-intercept gives log C, for C>0. Similarly, if log x_n grows like a polynomial in n, do the 
same with log log x_n versus log n. 

However, if the leading growth (of x_n or log x_n) involves a mixture of powers of log n and powers of n 
then a more delicate analysis is needed to measure leading coefficients and exponents (look at log n! and compare 
with Stirling's formula, for example). 

All the best,
From: SeqFan [seqfan-bounces at list.seqfan.eu] on behalf of Vladimir Reshetnikov [v.reshetnikov at gmail.com]
Sent: 07 May 2019 02:41
To: Sequence Fanatics Discussion list
Subject: [seqfan] Heuristic growth rate

Dear SeqFans,

Does anybody know of a tool that given a long enough segment of a "regular"
and "smooth" enough sequence can roughly estimate or predict its growth
rate? E.g. that a(n) ~ n^2 * log n, or a(n) ~ 3^n / sqrt(n) and such. I
intend to use its result as an initial hint to find and prove the actual
asymptotic of a sequence.

Best regards
Vladimir Reshetnikov

Seqfan Mailing list - http://list.seqfan.eu/

More information about the SeqFan mailing list