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!)
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
Hsien-Kuei Hwang, Svante Janson, and 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.
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)
PROG
(Python)
from functools import cache
@cache
def b(n): return 0 if n == 0 else b(n//2) + b((n-1)//2) + n + 2 + (n&1)
def a(n): return b(n-1)
print([a(n) for n in range(1, 53)]) # Michael S. Branicky, Aug 08 2022
CROSSREFS
Sequence in context: A312560 A312561 A312562 * A312563 A312564 A312565
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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 00:26 EDT 2024. Contains 371264 sequences. (Running on oeis4.)