Question 1. [4 MARKs] Consider the following algorithm: EXP(a, b,p): # Computes and returns ab mod p i, 2. if b mod 2 = 1: # i.e., b is odd if b = 0: return 1 x = EXP(a, (0-1)/2, p) return (x x a) mod p 4, else: x = EXP(a,b/2, p) return (z x) mod p 5, Give a recurrence relation for the exact number of multiplication operations ("x") performed by this algorithm on inputs of size n, in the worst-case. Explain what you are doing, i.e., state what n is equal to (in terms of the algorithm's variables), and what part of the algorithm is represented by each term in your recurrence (use the line numbers to the left of each line for easy reference). Do NOT try to give a closed-form solution for your recurrence! All we want is the recurrence itself Question 1. [4 MARKs] Consider the following algorithm: EXP(a, b,p): # Computes and returns ab mod p i, 2. if b mod 2 = 1: # i.e., b is odd if b = 0: return 1 x = EXP(a, (0-1)/2, p) return (x x a) mod p 4, else: x = EXP(a,b/2, p) return (z x) mod p 5, Give a recurrence relation for the exact number of multiplication operations ("x") performed by this algorithm on inputs of size n, in the worst-case. Explain what you are doing, i.e., state what n is equal to (in terms of the algorithm's variables), and what part of the algorithm is represented by each term in your recurrence (use the line numbers to the left of each line for easy reference). Do NOT try to give a closed-form solution for your recurrence! All we want is the recurrence itself