Consider the following algorithm for multiplying two n-bit numbers a and b, where n is a power of 2: 3 4 function SlowM(a, b, nl) 1 if n=1 then 2 if b = 1 then return(a) if b = -1 then return(-a) return 0 5 m n/2 6 al + a div 2m %the m most significant bits of a al + a rem 2m %the m least significant bits of a 8 bl + b div 2m %the m most significant bits of b 9 60+ b rem 2m %the m least significant bits of b 10 ct SlowMal, 61, m) 11 d SlowMa0, 60,m) 12 et SlowM(a0,61, m) 13 / + SlowMal, b0, m) 14 return e x 2 + (e + D) x 2m +d 7 1. Give a recurrence describing a good upper bound on the worst case number of bit operations that SlowM performs to multiply two na-bit numbers. You may assume that the number of bit operations to add or subtract two n-bit numbers is at most S(n) E O(n) and the time to shift a number (including multiplying and dividing by a power of 2) is s 0(1). Briefly justify your answer. 2. Use the Master Method to get a solution to your recurrence