Consider the problem of multiplying two large integers a and b with n bits each (they...

 

Transcribed Image Text:

Consider the problem of multiplying two large integers a and b with n bits each (they are so large in terms of digits that you cannot store them in any basic data type like long long int or similar). You can assume that addition, substraction, and bit shifting can be done in linear time, i.e., in (n). (a) (2 points) Derive the asymptotic time complexity depending on the number of bits n for a brute-force implementation of the multiplication. (b) (4 points) Derive a Divide & Conquer algorithm for the given problem by splitting the problem into two subproblems. For simplicity you can assume n to be a power of 2. (c) (1 point) Derive a recurrence for the time complexity of the Divide & Conquer algorithm you developed for subpoint (b). (d) Bonus (2 points) Solve the recurrence in subpoint (c) using the recursion tree method. (e) (1 point) Validate the solution in subpoint (d) by using the master theorem to solve the recurrence again. Consider the problem of multiplying two large integers a and b with n bits each (they are so large in terms of digits that you cannot store them in any basic data type like long long int or similar). You can assume that addition, substraction, and bit shifting can be done in linear time, i.e., in (n). (a) (2 points) Derive the asymptotic time complexity depending on the number of bits n for a brute-force implementation of the multiplication. (b) (4 points) Derive a Divide & Conquer algorithm for the given problem by splitting the problem into two subproblems. For simplicity you can assume n to be a power of 2. (c) (1 point) Derive a recurrence for the time complexity of the Divide & Conquer algorithm you developed for subpoint (b). (d) Bonus (2 points) Solve the recurrence in subpoint (c) using the recursion tree method. (e) (1 point) Validate the solution in subpoint (d) by using the master theorem to solve the recurrence again.

Answer rating: 100% (QA)

a Brute Force Time Complexity The bruteforce approach for multiplying two nbit integers involves multiplying each bit of one number with each bit of t... View the full answer