The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 (list; graph; refs; listen; history; text; internal format)
 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. LINKS Table of n, a(n) for n=2..55. 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 CROSSREFS Cf. A001620, A190186, A190187, A190194, A350428, A350568, A350569. Sequence in context: A024403 A129230 A203567 * A071404 A074133 A215909 Adjacent sequences: A350657 A350658 A350659 * A350661 A350662 A350663 KEYWORD nonn AUTHOR Hugo Pfoertner, Feb 01 2022 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified April 18 09:35 EDT 2024. Contains 371779 sequences. (Running on oeis4.)