login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons 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. 14
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.)

LINKS

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

Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi 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.

Hsien-Kuei Hwang, Svante Janson, Tsung-Hsi Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms 13:4 (2017), #47.

Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple generating functions, 2004.

Ralf Stephan, Table of generating functions (ps file).

Ralf Stephan, Table of generating functions (pdf file).

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.

From Ralf Stephan, Oct 24 2003: (Start)

a(n) = A076178(n-1) + 4*(n-1) for n >= 1.

a(n) = b(n-1) for n >= 1, where b(0) = 0, b(2*n) = b(n) + b(n-1) + 2*n + 2, b(2*n+1) = 2*b(n) + 2*n + 4.

(End)

CROSSREFS

Cf. A063090, A076178, A093418, A096620, A115107, A288964.

Sequence in context: A312560 A312561 A312562 * A312563 A312564 A312565

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 26 01:49 EDT 2021. Contains 346294 sequences. (Running on oeis4.)