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
Michael S. Branicky, Table of n, a(n) for n = 1..10000
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, and 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)
PROG
(Python)
from functools import cache
@cache
def b(n): return 0 if n == 0 else b(n//2) + b((n-1)//2) + n + 2 + (n&1)
def a(n): return b(n-1)
print([a(n) for n in range(1, 53)]) # Michael S. Branicky, Aug 08 2022
CROSSREFS
KEYWORD
nonn
AUTHOR
Karla J. Oty (oty(AT)uscolo.edu), Feb 05 2002
STATUS
approved