In Section 2.1 we described an algorithm that multiplies two n-bit binary integers x and y in time na, where a = log2 3. Call this procedure
fastmultiply (x, y).
(a) We want to convert the decimal integer 10n (a 1 followed by n zeros) into binary. Here is the algorithm (assume n is a power of 2):
if n = 1: return 10102
z = ???
return fastmultiply(z, z)
Fill in the missing details. Then give a recurrence relation for the running time of the algorithm, and solve the recurrence.
(b) Next, we want to convert any decimal integer x with n digits (where n is a power of 2) into binary. The algorithm is the following:
if n = 1: return binary[x]
split x into two decimal numbers xL, xR with n/2
binary [∙] is a vector that contains the binary representation of all one-digit integers. That is,
binary = 02,
binary = 12, up to
binary = 10012. Assume that a lookup in binary takes O(1) time. Fill in the missing details. Once again, give a recurrence for the running time of the algorithm, and solve it.