OFFSET
0,4
COMMENTS
The recurrence defining this sequence arises in the study of the Merge Sort algorithm. By the master theorem, a(n) is in BigTheta(n*log_2(n)).
MAPLE
a[0]:=0: for n from 1 to 101 do a[n]:=2*a[floor(n/2)] + n-1; od: seq( a[n], n=0..101);
MATHEMATICA
a[0]=0; a[n_]:=2*a[Floor[n/2]]+n-1; Table[a[n], {n, 0, 61}] (* James C. McMahon, Nov 09 2024 *)
CROSSREFS
KEYWORD
nonn,changed
AUTHOR
Peter C. Heinig (algorithms(AT)gmx.de), Oct 21 2006
EXTENSIONS
Missing a(0) inserted by James C. McMahon, Nov 09 2024
STATUS
approved