A200311 Number of comparisons needed for optimal merging of 2 elements with n elements.

2, 3, 4, 5, 5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13

Offset

1,1

References

R. L. Graham, On sorting by comparisons, in Proceedings of the ATLAS Symposium, 1971, pp. 263-269; http://www.math.ucsd.edu/~ronspubs/71_07_sorting.pdf.

F. K. Hwang and S. Lin, Optimal merging of 2 elements with n elementsw, Acta Informatica, 1 (1971), 145-158.

Links

Table of n, a(n) for n=1..83.

Index entries for sequences related to sorting

Formula

Let f(i) = A200310(i). Then for i in the range f(n-1)+1 through f(n), a(i) = n.

Maple

s:=[2, 3];
for n from 4 to 13 do
  for i from A200310(n-1)+1 to A200310(n) do s:=[op(s), n]; od:
od:

Crossrefs

Cf. A200310, A239100.

Sequence in context: A365092 A096365 A319412 * A007600 A195872 A091333

Adjacent sequences: A200308 A200309 A200310 * A200312 A200313 A200314

Keyword

nonn

Author

N. J. A. Sloane, Nov 15 2011

Status

approved