The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons 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. 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 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, 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). 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) CROSSREFS Cf. A063090, A076178, A093418, A096620, A115107, A288964. 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
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified July 26 01:49 EDT 2021. Contains 346294 sequences. (Running on oeis4.)