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, 268, 276, 292, 300

Offset: 0

Author

Don Knuth, Jul 28 2011

Keywords

• nonn

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.

Crossrefs

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

Cf. A048896 (first differences), A006046.

Programs

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}]]

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

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

Extensions

Third formula corrected by Don Knuth, Dec 08 2011