This site is supported by donations to The OEIS Foundation.

 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. 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; 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.) Hsien-Kuei Hwang, S Janson, TH 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; http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf. Also Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585 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, Oct 24 2003 CROSSREFS Sequence in context: A312560 A312561 A312562 * A312563 A312564 A312565 Adjacent sequences:  A067696 A067697 A067698 * A067700 A067701 A067702 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 | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified October 16 13:07 EDT 2018. Contains 316263 sequences. (Running on oeis4.)