the algorithm has to have O(logn) bound, better use divide and conquer Given a n
ID: 3837093 • Letter: T
Question
the algorithm has to have O(logn) bound, better use divide and conquer
Given a number n greaterthanorequalto 1 and a (user-specified) error tolerance e, you want to approximate the square root of n to within error tolerance e. Specifically, you want to return an x Squareroot n that satisfies |x^2 - n| lessthanorequalto e. For example, to compute the square root of n = 2 with e = 0.01, an acceptable answer would be x = 1.414 because 1.414^2 = 1.999396. Note that x = 1.415 is also acceptable, as 1.415^2 = 2.002225, but you only need to return a single answer Assume that you can't perform any arithmetic functions other than addition, subtraction, multiplication, and division. Write pseudocode for an efficient algorithm to solve this problem. Briefly justify a good asymptotic bound on the runtime of your algorithm in terms of n (i.e., give a runtime in terms of n assuming a fixed value of e). BONUS: Provide an asymptotic bound on the runtime of your algorithm in terms of e, for a fixed value of n Prove your result.Explanation / Answer
Pseudo code:
Initialize, start = 0, end = number, mid = (start+end)/2.
2. Set prevMid = 0, as the previous mid value.
3. Find diff = absolute difference between prevMid and mid.
4. While mid is not the square root of number (i.e. mid*mid == number) or difference diff is greater than 0.0005,
repeat the following steps:
a. If mid*mid > number, then the square root will be less than mid. So, set end = mid.
b. Else, the square root will be greater than mid. So, set start = mid.
c. Set prevMid = mid
d. Re-evaluate mid = (start+end)/2.
e. Re-evaluate diff from prevMid and mid.
Program:
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.