|
|
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
|
|
|
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.
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)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Karla J. Oty (oty(AT)uscolo.edu), Feb 05 2002
|
|
STATUS
|
approved
|
|
|
|