login
A350660
a(n) is the average number of key comparisons, rounded to the nearest integer, required to sort n records with distinct keys using bubble sort (Algorithm B in Don Knuth's TAOCP Vol. 3).
1
1, 3, 5, 9, 13, 18, 24, 31, 39, 48, 58, 69, 80, 93, 107, 121, 137, 153, 171, 189, 209, 229, 251, 273, 297, 321, 346, 373, 400, 428, 458, 488, 519, 551, 584, 619, 654, 690, 727, 765, 804, 845, 886, 928, 971, 1015, 1060, 1106, 1153, 1201, 1250, 1300, 1351, 1403
OFFSET
2,2
REFERENCES
D. E. Knuth, The Art of Computer Programming Second Edition. Vol. 3, Sorting and Searching. Chapter 5.2.2 Sorting by Exchanging, pages 106-109, 128-130. Addison-Wesley, Reading, MA, 1998.
FORMULA
a(n) = round(b(n)).
b(n) = binomial(n+1,2) - A190186(n)/A190187(n).
b(n) = binomial(m,2) - ((m/2)*(log(m) + gamma +log(2)) - 2*sqrt(2*Pi*m)/3 + 49/36 + O(n^(-1/2))) with gamma = A001620, and m = n + 1 (Knuth's asymptotic formula (37), TAOCP vol. 3, page 130).
a(n)/n^2 -> 1/2 for n -> infinity.
EXAMPLE
n b(n)
| | a(n)=
| | round(b(n))
| | | b(n)/n^2
2 1/1 1 0.2500
3 8/3 3 0.2963
4 31/6 5 0.3229
5 128/15 9 0.3413
6 1151/90 13 0.3552
7 11309/630 18 0.3663
8 17303/720 24 0.3755
9 1408073/45360 31 0.3832
10 2526503/64800 39 0.3899
100 4768 0.4768
1000 496458 0.4965
10000 0.4995
100000 0.4999
1000000 0.5000
KEYWORD
nonn
AUTHOR
Hugo Pfoertner, Feb 01 2022
STATUS
approved