login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A007077 Optimal cost of search tree for searching an ordered array of n elements with cost k of probing element k.
(Formerly M3379)
2
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 11 00:03 EDT 2021. Contains 342877 sequences. (Running on oeis4.)