|
Search: id:A158466
|
|
|
| A158466 |
|
Numerators of EH(n), the expected value of the height of a probabilistic skip list with n elements and p=1/2. |
|
+0
2
|
|
| 0, 2, 8, 22, 368, 2470, 7880, 150266, 13315424, 2350261538, 1777792792, 340013628538, 203832594062416, 131294440969788022, 822860039794822168, 177175812995012739374, 231553634961214157747264
(list; graph; listen)
|
|
|
OFFSET
|
0,2
|
|
|
COMMENT
|
A probabilistic skip list is data structure for sorted elements with O(log n) average time complexity for most operations.
|
|
LINKS
|
Wikipedia "Skip list"
William Pugh "Skip lists: a probabilistic alternative to balanced trees." Communications of the ACM, v.33 n.6, p.668-676, June 1990
Poblete, P. V.; Munro, J. I.; Papadakis, T. "The binomial transform and the analysis of skip lists." Theor. Comput. Sci. 352, 1 (Mar. 2006), 136-158.
|
|
FORMULA
|
EH(n) = Sum_{k=1..infinity} k * ((1-(1/2)^k)^n - (1-(1/2)^(k-1))^n).
EH(n) = -Sum_{k=1..n} (-1)^k * C(n,k) / (1-(1/2)^k).
|
|
EXAMPLE
|
0, 2, 8/3, 22/7, 368/105, 2470/651, 7880/1953, 150266/35433, 13315424/3011805, 2350261538/513010785, 1777792792/376207909 ... = A158466/A158467
|
|
MAPLE
|
EH:= n-> -sum ((-1)^k *binomial(n , k) /(1-(1/2)^k), k=1..n): seq (numer(EH(n)), n=0..20);
|
|
CROSSREFS
|
Denominators of EC(n): A158467
Sequence in context: A072929 A053958 A151356 this_sequence A065694 A161463 A014285
Adjacent sequences: A158463 A158464 A158465 this_sequence A158467 A158468 A158469
|
|
KEYWORD
|
frac,nonn
|
|
AUTHOR
|
Alois P. Heinz (heinz(AT)hs-heilbronn.de), Mar 19 2009
|
|
|
Search completed in 0.002 seconds
|
