Here is pseudocode for an algorithm Pow that takes two nonnegative integers a and n, and returns the value of an. POW(a,n) 123456result=1i=1whileinresult=resultai=i+1returnresult Prove that the algorithm PoW is correct by using the following loop invariant: result is the value of a(i1). In each of the following situations, indicate whether f=O(g), or f=(g), or both (in which case f=(g) ) by circling one of the symbols in the third column. Problem 3 (20 Points) Suppose you are choosing between the following three divide-and-conquer algorithms that. solve the same problem: - Algorithm A solves an instance of size n by dividing it into 8 instances of size n/2 in O(n2)-time, recursively solving each of the smaller instances, and then combining the solutions to the smaller instances in O(n)-time. - Algorithm B solves an instance of size n by dividing it into four instances of size n/4 in O(1)-time, recursively solving each of the smaller instances, and then combining the solutions to the smaller instances in O(n)-time. - Algorithm C solves an instance of size n by dividing it into five instances of size n/2 in O(logn)-time, recursively solving each of the smaller instances, and then combining the solutions to the smaller instances in O(n2)-time. Part 1 (15 Points): Use the master method to find the running-times of each of these problems tsing O-notation? - Algorithm A Running Time: - Algorithm B Running Time - Algorithm C Running Time: Part 2 (5 Points): Which algorithm has the fastest running time? Problem 4 (30 Points) Part 1 (20 Points): Give pseudocode for an O(logn)-time divide-and-conquer algorithm that takes a sorted array of distinct integers A[1,n], and returns an index i for which A[i]=i if one exists; otherwise it should return - 1 when no such index exists. Label each phise (basis, divide, conquer, combine) of your algorithm. Part 2 (10 Points): Prove that your algorithm runs in O(logn)-time