Consider the following piece of pseudocode: function NewMultiply(A,B,N) if(N == 0): return 0 else if (N...

  

Transcribed Image Text:

Consider the following piece of pseudocode: function NewMultiply(A,B,N) if(N == 0): return 0 else if (N = 1): return A[0]*B[0] h=floor(N/2) x=N mod 2 A1-new array (h+x) of zeroes B1=new array(h+x) of zeroes for x This piece of pseudocode computes the (decimal) integer obtained from multiplying the two arrays of length N storing bits. The operation floor (x) returns the largest integer smaller than or equal to x. (d) What is the worst-case time complexity of the function NewMultiply in terms of the length of the arrays N? Use Theta notation (1 mark) and show your working to arrive at this answer (6 marks). Assume that the floor of a number and x mod 2 can be computed in a constant number of time-steps. (7 marks) Consider the following piece of pseudocode: function NewMultiply(A,B,N) if(N == 0): return 0 else if (N = 1): return A[0]*B[0] h=floor(N/2) x=N mod 2 A1-new array (h+x) of zeroes B1=new array(h+x) of zeroes for x This piece of pseudocode computes the (decimal) integer obtained from multiplying the two arrays of length N storing bits. The operation floor (x) returns the largest integer smaller than or equal to x. (d) What is the worst-case time complexity of the function NewMultiply in terms of the length of the arrays N? Use Theta notation (1 mark) and show your working to arrive at this answer (6 marks). Assume that the floor of a number and x mod 2 can be computed in a constant number of time-steps. (7 marks)