A007077 Optimal cost of search tree for searching an ordered array of n elements with cost k of probing element k. (Formerly M3379)

1, 4, 10, 19, 31, 47, 68, 92, 120, 153, 190, 232, 279, 332, 392, 454, 521, 593, 670, 753, 841, 936, 1036, 1141, 1252, 1370, 1494, 1625, 1763, 1909, 2063, 2216, 2376, 2542, 2713, 2890, 3074, 3264, 3460, 3663, 3872, 4088, 4310, 4540, 4776, 5021

Offset

1,2

References

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

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

M. V. Connolly and W. J. Knight, Search in an array in which probe costs grow exponentially or factorially, Preprint. (Annotated scanned copy)

William J. Knight, Search in an ordered array having variable probe cost, SIAM J. Comput. 17 (1988), no. 6, 1203-1214.

W. J. Knight, Letter to N. J. A. Sloane, Jul. 1991

Index entries for sequences related to rooted trees

Index entries for sequences related to trees

Formula

a(n) = m(n, 0) where m(0, d) = 0 and for n > 0, m(n, d) = min_{1 <= r <= n} {(r+d) * n + m(r-1, d) + m(n-r, r+d)} [from Knight]. - Sean A. Irvine, Oct 07 2017

Crossrefs

Cf. A007078.

Sequence in context: A005448 A301247 A037040 * A301202 A301021 A009895

Adjacent sequences: A007074 A007075 A007076 * A007078 A007079 A007080

Keyword

nonn

Author

N. J. A. Sloane, Mira Bernstein

Extensions

More terms from Sean A. Irvine, Oct 07 2017

Status

approved