A122701 a(0)=0, a(n) = 2*a(floor(n/2)) + n - 1 for n > 0.

0, 0, 1, 2, 5, 6, 9, 10, 17, 18, 21, 22, 29, 30, 33, 34, 49, 50, 53, 54, 61, 62, 65, 66, 81, 82, 85, 86, 93, 94, 97, 98, 129, 130, 133, 134, 141, 142, 145, 146, 161, 162, 165, 166, 173, 174, 177, 178, 209, 210, 213, 214, 221, 222, 225, 226, 241, 242, 245, 246, 253, 254

Offset: 0

Author

Peter C. Heinig (algorithms(AT)gmx.de), Oct 21 2006

Keywords

• nonn

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)).

Crossrefs

Cf. A080277.

Programs

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 *)

Extensions

Missing a(0) inserted by James C. McMahon, Nov 09 2024