Write algorithms that solve the following exercises and analyze their running ti

Question

Write algorithms that solve the following exercises and analyze their running times. You may write actual code or pseudocode for each problem in this part.

An important problem in numerical analysis is to find a solution to the equation f (X ) = 0 for some arbitrary f . If the function is continuous and has two points low and high such that f (low ) and f (high ) have opposite signs, then a root must exist between low and high and can be found by a binary search. Write a function tha takes as parameters

Explanation / Answer

Algorithm :
Step 1: Initialize function, j as required.
Step 2: Input high and low
Step 3: calculate f(high) & f(low)
Step 4: check if f(high) & f(low) have opposite signs , then return true else false
Step 5: If step 4 returns True, call binary_search(f,high,low) and print the value returned by binary_search as root of the function.
Step 6: If step 4 returns False, print no roots of the function in given range

Binary_Search(f,high,low)
Step 1: calculate mid = (high + low)/2
Step 2: check if f(mid) id equal to 0, if yes return mid as this is the root else move to step 3
Step 3: check if f(mid) is less than zero, if yes then recursively call binary_search(f,high,mid+1) else move to step 4
Step 4: as f(mid) is greater than 0, recursively call binary_search(f,mid-1,low)

As no particular language was provided I have given the Algorithmn for given problem.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.