A122701 - OEIS

%I #4 Dec 06 2019 21:42:25

%S 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,

%T 85,86,93,94,97,98,129,130,133,134,141,142,145,146,161,162,165,166,

%U 173,174,177,178,209,210,213,214,221,222,225,226,241,242,245,246,253,254

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

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

%p T[0]:=0; for n from 1 to 101 do T[n]:=2*T[floor(n/2)] + n-1; od; seq( T[n], n=1..101);

%Y Cf. A080277.

%K nonn

%O 0,3

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