Question

If someone can help with 3

3) To multiply 2 n bit binary numbers the straightforward way takes (r) time because each digit of each number multiplies each digit of the other number. (The aditions from carying are lower order terms.) Consider the following divide- and-conquer algorithm, which assumes, for simplicity, that n is a power of 2: Split each number into 2 collections of bits, the high order bits and the low order bits. For convenience, call the two High & Low for one number and high & low for the other. Form the four products Hh- High x high, HI - High x low, Lh-Low x high and LI = Low x low. Add the four together after first shifting Hi and Lh left by n 2 bits and HL by n bits. Done. Again, the shifting and adding are lower order. The recurrence relation for this algorithm is (8 pts.) a) T(1)= T(n) = b) This has solution T(n)-_). Show this directly or by using the Master method. (4 pts.)

Answer 1

0v) (th yu, Lh,LL) 4 2 2 Total bib HL