cp's OEIS Frontend

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

%I A193494 #57 Feb 16 2025 08:33:15
%S A193494 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,
%T A193494 73,77,85,89,97,105,121,122,124,126,130,132,136,140,148,150,154,158,
%U A193494 166,170,178,186,202,204,208,212,220,224,232,240,256,260,268,276,292,300
%N A193494 Worst case of an unbalanced recursive algorithm over all n-node binary trees.
%C A193494 Solves the recurrence a(0) = 0, a(n+1) = 1 + Max_{0 <= k <= n-k} (2*a(k) + a(n-k)).
%C A193494 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
%D A193494 (I think I've seen it years ago, but I have no idea where.)
%H A193494 Charles R Greathouse IV, <a href="/A193494/b193494.txt">Table of n, a(n) for n = 0..10000</a>
%H A193494 Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, <a href="https://arxiv.org/abs/2210.10968">Identities and periodic oscillations of divide-and-conquer recurrences splitting at half</a>, arXiv:2210.10968 [cs.DS], 2022, p. 30.
%H A193494 Don Knuth: I may refer to this sequence in my <a href="http://www-cs-faculty.stanford.edu/~knuth/musings.html">"Christmas tree lecture"</a> this year (2011).
%H A193494 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Rule126.html">Rule 126.</a>
%F A193494 a(n) = O(n^(log_2(3)));
%F A193494 a(n) = 2^(nu(n)-1) + a(n-1) when n>0 and has nu(n) 1-bits in binary (A000120);
%F A193494 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;
%F A193494 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.
%F A193494 a(n) = (A006046(n+1) - 1) / 2. - _Kevin Ryde_, Jan 30 2022
%p A193494 a:= proc(n) option remember;
%p A193494       `if`(n=0, 0, 1 +max(seq(2*a(k)+a(n-1-k), k=0..(n-1)/2)))
%p A193494     end:
%p A193494 seq(a(n), n=0..60); # _Alois P. Heinz_, Jul 29 2011
%t A193494 a[0]=0; a[n_]:=a[n]=1+Max[Table[2a[k]+a[n-1-k],{k,0,(n-1)/2}]]
%o A193494 (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
%Y A193494 log_2(a(n) - a(n-1)) is A000120(n) - 1, for n > 0.
%Y A193494 Cf. A048896 (first differences), A006046.
%K A193494 nonn
%O A193494 0,3
%A A193494 _Don Knuth_, Jul 28 2011
%E A193494 Third formula corrected by _Don Knuth_, Dec 08 2011