|
Search: id:A001855
|
|
|
| A001855 |
|
Maximal number of comparisons for sorting n elements by binary insertion.
(Formerly M2433 N0963)
|
|
+0
14
|
|
| 0, 1, 3, 5, 8, 11, 14, 17, 21, 25, 29, 33, 37, 41, 45, 49, 54, 59, 64, 69, 74, 79, 84, 89, 94, 99, 104, 109, 114, 119, 124, 129, 135, 141, 147, 153, 159, 165, 171, 177, 183, 189, 195, 201, 207, 213, 219, 225, 231, 237, 243, 249, 255, 261, 267, 273, 279, 285
(list; graph; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
Equals n-1 times the expected number of probes for a successful binary search in a size n-1 list.
Piecewise linear: breakpoints at powers of 2 with values given by A000337.
a(n) is the number of digits in the binary representation of all the numbers 1 to n-1. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Dec 05 2006
|
|
REFERENCES
|
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, Sect 5.3.1, Eq. (3); Sect. 6.2.1 (4).
J. W. Moon, Topics on Tournaments. Holt, NY, 1968, p. 48.
Tianxing Tao, Om optimal arrangement of 12 points, pp. 229-234 in Combinatorics, Computing and Complexity, ed. D. Du and G. Hu, Kluwer, 1989.
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n=1..1000
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
R. Stephan, Some divide-and-conquer sequences ...
R. Stephan, Table of generating functions
Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
Index entries for sequences related to sorting
|
|
FORMULA
|
Let n = 2^(k-1) + g, 0 <= g < 2^(k-1); then a(n) = 1 + n*k - 2^k. - njas, Dec 01 2007
a(n) = Sum_{k=1..n} ceiling(log_2 k) = n*ceiling(log_2 n) - 2^ceiling(log_2(n)) + 1.
a(n)=a(floor(n/2))+a(ceiling(n/2))+n-1.
G.f.: x/(1-x)^2 * Sum(k>=0, x^2^k). - Ralf Stephan (ralf(AT)ark.in-berlin.de), Apr 13 2002
a(1)=0, for n>1, a(n)=ceiling(n*a(n-1)/(n-1)+1) - Benoit Cloitre (benoit7848c(AT)orange.fr), Apr 26 2003
a(n) = n-1 + min { a(k)+a(n-k) : 1 <= k <= n-1 }, cf. A003314. - Vladeta Jovovic (vladeta(AT)Eunet.yu), Aug 15 2004
a(n) = A061168(n-1)+n-1 for n>1 - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Dec 05 2006
|
|
MAPLE
|
Digits:=200; f:=proc(n) local k, x; x:=floor(log(n)/log(2)); k:=x+1; 1+n*k-2^k; end; - njas, Dec 01 2007
|
|
PROGRAM
|
(PARI) a(n)=if(n<2, 0, n-1+a(n\2)+a((n+1)\2))
(PARI) a(n)=local(m); if(n<2, 0, m=length(binary(n-1)); n*m-2^m+1)
|
|
CROSSREFS
|
Partial sums of A029837.
Cf. A003071, A000337, A030190, A030308, A061168.
Cf. A061168.
Adjacent sequences: A001852 A001853 A001854 this_sequence A001856 A001857 A001858
Sequence in context: A102696 A130262 A094228 this_sequence A006591 A052488 A076372
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
njas
|
|
EXTENSIONS
|
Additional comments from M. D. McIlroy (mcilroy(AT)dartmouth.edu).
|
|
|
Search completed in 0.002 seconds
|
