Problem 3 (15 points) N people are standing in an arced bridge as shown in the figure alongside. We define the "height" h, of person i to be its distance from the base of the bridge. For simplicity assume their positions, from left to right, are given to you and they are unique. [10 points] Your goal is to locate the person with the tallest height. Clearly (why?) this problem can be solved easily in time O(N), but here you have to solve this problem in time O(log N) using a Divide&Conquer algorithm For full credit, you need to: 1. (3 points) Give a high level description of your algorithm. How do you Heights of each person handle the base cases? 2. (3 points) Explain carefully why your algorithm is correct 3. (4 points) Justify the recurrence Tn) of its running time and solve it using any method we learned in class. [5 points] Is the O(log N) algorithm optimal? Argue why or why not