login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A067699 Number of comparisons made in a version of the sorting algorithm QuickSort for an array of size n with n identical elements. 0
0, 4, 8, 14, 18, 24, 30, 38, 42, 48, 54, 62, 68, 76, 84, 94, 98, 104, 110, 118, 124, 132, 140, 150, 156, 164, 172, 182, 190, 200, 210, 222, 226, 232, 238, 246, 252, 260, 268, 278, 284, 292, 300, 310, 318, 328, 338, 350, 356, 364, 372, 382 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

REFERENCES

Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest. Introduction to Algorithms. McGraw-Hill Book Company, 2000. (Gives description of this version of QuickSort.)

Hsien-Kuei Hwang, S Janson, TH Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint, 2016; http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf. Also Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585

LINKS

Table of n, a(n) for n=1..52.

R. Stephan, Some divide-and-conquer sequences ...

R. Stephan, Table of generating functions

FORMULA

a[n]=2*Ceiling[(n+1)/2]+a[Ceiling[n/2]]+a[Floor[n/2]] with a[1]=0, a[2]=4 and a[3]=8

A076178(n-1) + 4(n-1). a(n) = b(n-1) with b(0)=0, b(2n) = b(n)+b(n-1)+2n+2, b(2n+1) = 2b(n)+2n+4. - Ralf Stephan, Oct 24 2003

CROSSREFS

Sequence in context: A022804 A189396 A189676 * A066941 A176949 A274968

Adjacent sequences:  A067696 A067697 A067698 * A067700 A067701 A067702

KEYWORD

nonn

AUTHOR

Karla J. Oty (oty(AT)uscolo.edu), Feb 05 2002

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified February 18 17:08 EST 2018. Contains 299325 sequences. (Running on oeis4.)