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

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

Author

N. J. A. Sloane, Mira Bernstein

Keywords

• nonn

References

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

Links

• 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

Crossrefs

Cf. A007078.

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

Extensions

More terms from Sean A. Irvine, Oct 07 2017