PROBLEM 2 - algorithm design (40 points) Find the Missing Integer 0..N kn w this aheadf time) . since there arenly N array entries and there are N+1 distinct values in O..N, exactly one of them must be missing from the array Your job: devise an O(log N) time algorithm to find the missing integer. HINT Think of a "binary-search-like" approach COMMENT You can present your algorithm as a c function but, you must also include an explanation of why it works -- i.e., the underlying logic of your solution. PROBLEM 3 - analysis (30 points): uickSort n n identical elements. Suppose thearray-based quicksort implementation given in class is applied to an array in which all nelements are identical Analyze the runtime of quicksort in this scenario.Give your answer using big-Theta notation and explain clearly how you arrived at your answer (i.e., convince us!) (The C++ implementation given in class also appears in Appendix B for reference)