|
Search: id:A067699
|
|
|
| A067699 |
|
Number of comparisons made in a version of the sorting algorithm QuickSort for an array of size n with n identical elements. |
|
+0
1
|
|
| 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; listen)
|
|
|
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: A024805 A008579 A022804 this_sequence A066941 A049420 A055507
Adjacent sequences: A067696 A067697 A067698 this_sequence A067700 A067701 A067702
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Karla J. Oty (oty(AT)uscolo.edu), Feb 05 2002
|
|
|
Search completed in 0.002 seconds
|
