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

Author

Hugo Pfoertner, Feb 01 2022

Keywords

• nonn

Examples

			        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
		

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.

Crossrefs

Cf. A001620, A190186, A190187, A190194, A350428, A350568, A350569.

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.