A193494 Worst case of an unbalanced recursive algorithm over all n-node binary trees.

0, 1, 2, 4, 5, 7, 9, 13, 14, 16, 18, 22, 24, 28, 32, 40, 41, 43, 45, 49, 51, 55, 59, 67, 69, 73, 77, 85, 89, 97, 105, 121, 122, 124, 126, 130, 132, 136, 140, 148, 150, 154, 158, 166, 170, 178, 186, 202, 204, 208, 212, 220, 224, 232, 240, 256, 260

Offset

0,3

Comments

Solves the recurrence a(0) = 0, a(n+1) = 1 + Max_{0 <= k <= n-k} (2*a(k) + a(n-k)).

a(floor(n/2)) is also the number of white areas in the elementary cellular automata based on rule 126 completed up to generation n. - Philippe Beaudoin, Feb 03 2014

References

(I think I've seen it years ago, but I have no idea where.)

Links

Charles R Greathouse IV, Table of n, a(n) for n = 0..10000

Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 30.

Don Knuth: I may refer to this sequence in my "Christmas tree lecture" this year (2011).

Eric Weisstein's World of Mathematics, Rule 126.

Formula

a(n) = O(n^(log_2(3)));

a(n) = 2^(nu(n)-1) + a(n-1) when n>0 and has nu(n) 1-bits in binary (A000120);

If n = 2^(e_1) + ... + 2^(e_t) with e_1 > ... > e_t >= 0, then a(n) = ((3^(e_1) + 2*3^(e_2) + ... + 2^(t-1)*3^(e_t) + 2^t-1)/2;

The generating function has the form (t_0 + t_0*t_1 + t_0*t_1*t_2 + ...)/ (1-z), where t_0 = z and t_k = z^{2^{k-1}} + 2*z^{2^k} for k > 0.

a(n) = (A006046(n+1) - 1) / 2. - Kevin Ryde, Jan 30 2022

Maple

a:= proc(n) option remember;
      `if`(n=0, 0, 1 +max(seq(2*a(k)+a(n-1-k), k=0..(n-1)/2)))
    end:
seq(a(n), n=0..60); # Alois P. Heinz, Jul 29 2011

Mathematica

a[0]=0; a[n_]:=a[n]=1+Max[Table[2a[k]+a[n-1-k], {k, 0, (n-1)/2}]]

Prog

(PARI) a=vector(60); a[1]=0; for(n=0, #a-2, a[n+2]=1+vecmax(vector(n\2+1, k, 2*a[k]+a[n-k+2]))); a \\ Charles R Greathouse IV, Jul 29 2011

Crossrefs

log_2(a(n) - a(n-1)) is A000120(n) - 1, for n > 0.

Cf. A048896 (first differences), A006046.

Sequence in context: A288511 A249058 A105771 * A161832 A350592 A078404

Adjacent sequences: A193491 A193492 A193493 * A193495 A193496 A193497

Keyword

nonn

Author

Don Knuth, Jul 28 2011

Extensions

Third formula corrected by Don Knuth, Dec 08 2011

Status

approved