this corse Design and Analysis of Algorithms

Q3. [20 pts] Designing and Implementing an Algorithm - Sum of three elements a. [8 pts] Write an algorithm that determines whether there are three elements in a given array of integers that sums to exactly a given integer value k. As input, you are given an array of n integers and an integer value k. (Note that the efficiency of your algorithm will be considered in grading). For example, given the array [1, 3, 7, 4] and k = 14, the answer is yes, given k = 6 the answer is "no. b. [5 pts] Identify a basic operation for your algorithm and study the performance of your algorithm by giving its time complexity function. If it has an every-case time complexity, determine it. Otherwise, determine the worst-case time complexity. c. [2 pts] Identify the complexity category to which the algorithm belongs. d. [5 pts] Implement your algorithm using Java. Write a main method that asks the user to enter the integer value k and the size n of an array of integers. The main method must generate the array elements randomly. As output, the program must first print all elements of the array. Then, it should print No if the array does not contain three elements that sums to k or print Yes if there are three elements that sums to k. If the output is Yes, the program must print these three elements and their location index in the array