A067699 Number of comparisons made in a version of the sorting algorithm QuickSort for an array of size n with n identical elements.

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

Offset: 1

Author

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

Keywords

• nonn

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

• Michael S. Branicky, Table of n, a(n) for n = 1..10000
• 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, 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.
• 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).

Crossrefs

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

Programs

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

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)