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

 

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 7 14:13 EDT 2022. Contains 357271 sequences. (Running on oeis4.)