2. 14marks Consider the following algorithm based on the divide and conquer strategy which, given three positive integers x, n and p where n is a power of 2, 2 (Le. that n 2 for k1), finds the remainder when x is divided by p. Imputs: Three positive integers x, n and p, where n-2 for some k1 Output: The remainder when x is divided by p int findRemint x, int n, int p) int r if (n2) retun (xx) mod p else rfindRemx, n/2, pl retun () mod p 3 Do a worst-case analysis for the above algorithm. Of course, assume that n is a power of 2, i.e -2 for some k. Do the folllowing as part of your analysis: a 4 marks Write a recursive formula for the worst-case malysis of this algorithm (don’t forget your base case in this formula). As your basic operation counted use divisions multiplications and mumber of mod function calls b) [4 marks] Through back substitution, solve the recurrence relation from a). Please show your work, and follow the method as shown in class S marks c) Verify your solution found in b) using induction marks d) What is the complexity of this algorithm? You just need to state your answer here