(a)   当n=1时，(10)d=(1010)b

当n=2时，(100)d=(10)d x (10)d=(1010)b x (1010)b

当n=4时，(10000)d=(100)d x (100)d=(1010)b x (1010)b x (1010)b x (1010)b

…

因此z=pwr2bin(n/2)

T(n)=T(n/2)+(cn/2)^log23=>T(n)=O(n^log23)

(b)

若十进制整数x的位数等于1,则返回binary[x]

假设位数为n(n>1且n为2的幂)，则把x平均分成两部分x_L和x_R,每一部分为n/2位

则x=10^n/2*x_L+x_R=pwr2bin(n/2)*dec2bin(x_L)+dec2bin(x_R)

=fastMultiply(pwr2bin(n/2),dec2bin(x_L))+dec2bin(x_R)

运行时间为

T(n)=2T(n)+O(n^log23)=>T(n)=O(n^log23)