The response by Ebenezer isn\'t correct for computing the above problem. Nor is

Question

The response by Ebenezer isn't correct for computing the above problem. Nor is the constant factor supplied or the time efficiency. Thank you for trying though.

Design a decrease-by-constant-factor algorithm for computing [log3n] where n > 0, and determine its time efficiency. Explain why this is a decrease-by-constant-factor algorithm, and specify the factor. The response by Ebenezer isn't correct for computing the above problem. Nor is the constant factor supplied or the time efficiency. Thank you for trying though.

Explanation / Answer

Dear..

The algorithm is quite similar to binary search, of course. In the worst case, And key comparisons does it make on each iteration.

Assume for a maximum of f(x) and that we know the maximum lies somewhere between A and B. For the algorithm to be applicable, there must be some value x such that
for all a,b with A = a < b = x, we have f(a) < f(b), and
for all a,b with x = a < b = B, we have f(a) > f(b).

The algorithm

ALGORITHM ternarySearch(f, left, right, absolutePrecision)
//left and right are the current bounds; the maximum is between them
if (right-left < absolutePrecision) return (left+right)/2
leftThird := (left*2+right)/3
rightThird := (left+right*2)/3
if (f(leftThird) < f(rightThird))
return ternarySearch(f, leftThird, right, absolutePrecision)
else
return ternarySearch(f, left, rightThird, absolutePrecision)
end

A ternary search is an example of a divide and conquer algorithm.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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