Imagine a "feature limited" processor that supports the following operations (in addition to the usual logical tests, if-then-else control flow, etc.): - addition, i.e., x+y for positive integers x,y; - right-shifts by 1 , i.e., x1:=x/2 for positive integers x; and - parity, i.e., xmod2, for positive integers x. However, the processor does not have an operation for integer multiplication. So, we want to implement multiplication using the provided operations. For simplicity, we consider implementing just the special case of 376x, given a positive integer input x. (a) What is the (worst-case, asymptotic) running time of following multiplication algorithm, given an n-bit input? (You may assume that addition takes constant time.) Is this an "efficient" algorithm, in the sense adopted by this class? 1: function NavePROD (x, a positive integer ) 2: if x=1 then return 376 3: return 376+ NaVEPROD (x1) (b) Give pseudocode for a divide-and-conquer algorithm for the problem that performs just O(n) operations when given an n-bit input x. As always, convincingly justify its correctness and running time. Hint: we can double a number-i.e., multiply it by two-by adding the number to itself. If x is even, what number should be doubled to get the desired result 376x ? What can we do if x is odd