|
| |
|
|
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; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
REFERENCES
| For a description of the version of QuickSort see: Thomas H. Cormen, Charles E. Leiserson and Ronald L. Riverst. Introduction to Algorithms. McGraw-Hill Book Company, 2000.
|
|
|
LINKS
| 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 (ralf(AT)ark.in-berlin.de), Oct 24 2003
|
|
|
CROSSREFS
| Sequence in context: A022804 A189396 A189676 * A066941 A176949 A173522
Adjacent sequences: A067696 A067697 A067698 * A067700 A067701 A067702
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Karla J. Oty (oty(AT)uscolo.edu), Feb 05 2002
|
| |
|
|
