I need help with part 3. Suppose to take the fact that a binary search is conducted from part 2 into account.

Theory: Conditioning and Algorithmic Complexity 10 points Lets consider a functionfCx with absolute condition number Kabs on the intervalx E I0,ij, max lf '(x) You may assume that f has as many derivatives as needed. Given valuef, our goal will be to find all points El0, ij such thatfor) 3f. More precisely, we want to approximate each X, by finding a nearby such that thus bounding the absolute error by a given value E. n this problem is a bit atypical. To understand this choice, consider a functionfox) such that f(0) 1 and f(1) 1. What can we Part 0 Our use of absolute condition numbers say about its relative condition number on the intervalx E [0, 1]? Part 1 Lets try to approximate each x by brute-force search. Define equispaced points x ,xn on [0, ij. If lf Cxi) -fl S e, we have found a suitable approximation to some x How many points n do we need to find a suitable approximation for every Express your solution as a function of E and Kabs (Note: here and later we do not require a one-to-one mapping between approximations and target points.) Part 2 Now, lets assume f is strictly increasing on [0,1]. How many solutions can exist in this case? Describe an algorithm to approximate all of them in O(log(n)) time, where n is your solution to Part 1. Part 3 Finally, lets assume f s a polynomial of degree k. Thus, we know all k derivatives f for i E {1,2, k). Lets assume the absolute condition number Kabs holds for each derivative f )(x) on the interval x E [0, 11 and thatf #0. Provide an algorithm that computes the critical points off and uses them to find all solutions. overall, the algorithm should take O(k2 log(n)) time, where n is your solution to