Algorithm reccurence please do problem in full and give comp

Algorithm reccurence please do problem in full and give complete solution for good feedback

Problems to be handed in 1. (Lots of multiplications) Suppose you have to compute the product IT ri of n integers z1, ...,zn, each at most k bits long. You have a few choices to make: first you need to select which mutplication algorithm to use, and second, you need to decide the order in which you will carry out the multiplications that is, how you will parenthesize the expression There are three reasonable algorithms for multiplication (two of which we\'ve seen in class) The grade school algorithm: To multiply a p-bit integer times a g-bit integer, this algoithm uses e(pg) operations Karatsuba\'s algorithm: To multiply a p-bit integer times a q-bit integer where p q, this algorithm uses e log2 3 operations. The Fast Fourier Transform algorithm, which we did not cover in class. For the purposes of this exercise, you may assume that to multiply a p bit integer times a q-bit integer where p q, this algorithm uses e q log (g) operations (you don\'t need to know how it works, though you are welcome to read about it in Chapter 30 There are at least two natural ways to do this (a) The first is to do the multplications in the obvious order Algorithm 1: Straight-multiply (r1 z2, ...,zn) 1 prod f- zl; 2 for 2 to n do 3 prod multiply (prod, zi) multiply can be any of the three algorithms above. 4 return prod; The algorithm we saw in class took two inputs of the same size. how would you deal with the situation where

Solution

a) As given in hint also, if there are n numbers and to multiply them each takes k = O(1) also , then total time complexity will be O(n).

So using the algorithm mentioned in a) total running time complexity of each multipliucation algorithm will be :

Grade School : O(n*k*k)

Karatsuba : O(n*k^log₂3)

Fourier : O(n*k*log²k)

b) Here, Divide and conquer algorithm is used and hence time complexity is reduced.

Grade School : O(log₂n*k*k)

Karatsuba : O(log₂n*k^log₂3)

Fourier : O(log₂n*k*log²k)

c) Yes, The divide and conquer algorithm is always better as it provides less time complexity.