|
%I #32 Aug 08 2022 20:56:59
%S 0,4,8,14,18,24,30,38,42,48,54,62,68,76,84,94,98,104,110,118,124,132,
%T 140,150,156,164,172,182,190,200,210,222,226,232,238,246,252,260,268,
%U 278,284,292,300,310,318,328,338,350,356,364,372,382
%N Number of comparisons made in a version of the sorting algorithm QuickSort for an array of size n with n identical elements.
%D 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.)
%H Michael S. Branicky, <a href="/A067699/b067699.txt">Table of n, a(n) for n = 1..10000</a>
%H Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, <a href="http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf">Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications</a>, preprint, 2016.
%H Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, <a href="http://doi.org/10.1145/3127585">Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications</a>, ACM Transactions on Algorithms 13:4 (2017), #47.
%H Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences with (relatively) simple generating functions</a>, 2004.
%H Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions (ps file)</a>.
%H Ralf Stephan, <a href="/A067699/a067699.pdf">Table of generating functions (pdf file)</a>.
%F 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.
%F From _Ralf Stephan_, Oct 24 2003: (Start)
%F a(n) = A076178(n-1) + 4*(n-1) for n >= 1.
%F 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.
%F (End)
%o (Python)
%o from functools import cache
%o @cache
%o def b(n): return 0 if n == 0 else b(n//2) + b((n-1)//2) + n + 2 + (n&1)
%o def a(n): return b(n-1)
%o print([a(n) for n in range(1, 53)]) # _Michael S. Branicky_, Aug 08 2022
%Y Cf. A063090, A076178, A093418, A096620, A115107, A288964.
%K nonn
%O 1,2
%A Karla J. Oty (oty(AT)uscolo.edu), Feb 05 2002
|
