In this problem, we will analyze how many iterations it takes to find a square root...

 

Transcribed Image Text:

In this problem, we will analyze how many iterations it takes to find a square root to a given precision using binary search. (a) (5 points) Suppose we re-implemented the algorithm to go "digit-by- digit"; i.e. use binary search to figure out the first digit, then use binary search to figure out the second digit, and so on. If we want our answer to be correct up to n digits after the decimal point, how many guesses G(n) will we need to make? Justify your answer. (b) (2 points) Now, suppose we implemented our algorithm exactly as in class, where we iteratively guess midpoints of our possible range. If we want our answer to be correct up to one digit after the decimal point, how many guesses G(n) will we need to make? Justify your answer. (c) (2 points) Assume again that we implemented our algorithm as in class, and we want to be accurate to two digits after the decimal point. How many guesses G(n) will we need to make in the worst case? Justify your answer. (d) (1 point) Now, assume that we are implementing our algorithm just as in class and want our answer to be correct up to n digits. Establish and prove an upper bound on the number of guesses it will take to achieve this level of correctness. Try to get as small an upper bound as possible. In this problem, we will analyze how many iterations it takes to find a square root to a given precision using binary search. (a) (5 points) Suppose we re-implemented the algorithm to go "digit-by- digit"; i.e. use binary search to figure out the first digit, then use binary search to figure out the second digit, and so on. If we want our answer to be correct up to n digits after the decimal point, how many guesses G(n) will we need to make? Justify your answer. (b) (2 points) Now, suppose we implemented our algorithm exactly as in class, where we iteratively guess midpoints of our possible range. If we want our answer to be correct up to one digit after the decimal point, how many guesses G(n) will we need to make? Justify your answer. (c) (2 points) Assume again that we implemented our algorithm as in class, and we want to be accurate to two digits after the decimal point. How many guesses G(n) will we need to make in the worst case? Justify your answer. (d) (1 point) Now, assume that we are implementing our algorithm just as in class and want our answer to be correct up to n digits. Establish and prove an upper bound on the number of guesses it will take to achieve this level of correctness. Try to get as small an upper bound as possible.