Addition of two positive integers takes O(k) time by the standard addi- tion algorithm, with k...

 

Transcribed Image Text:

Addition of two positive integers takes O(k) time by the standard addi- tion algorithm, with k the total length of the representation in binary of the integers. The following recursive function M defines multiplication, X M(x,y) = 2* M(x,y/2) for y = 1 for y even x+2* M(x, (y-1)/2) for y odd and not 1 for positive integers x and y. For instance, M(6,5) = 6+2 * M(6, 2) = 6+2 * 2 * M(6, 1) = 6+2*2*6 = 30. Show that multiplication is in P-time by analyzing this algorithm. The run time will be in Big-Oh notation as a function of k, the total length of the representation in binary of the numbers. Addition of two positive integers takes O(k) time by the standard addi- tion algorithm, with k the total length of the representation in binary of the integers. The following recursive function M defines multiplication, X M(x,y) = 2* M(x,y/2) for y = 1 for y even x+2* M(x, (y-1)/2) for y odd and not 1 for positive integers x and y. For instance, M(6,5) = 6+2 * M(6, 2) = 6+2 * 2 * M(6, 1) = 6+2*2*6 = 30. Show that multiplication is in P-time by analyzing this algorithm. The run time will be in Big-Oh notation as a function of k, the total length of the representation in binary of the numbers.