Recursive Algorithm and Analysis Suppose company X has hired you as a software e

Question

Recursive Algorithm and Analysis Suppose company X has hired you as a software engineer. Company X is desperate to improve the run time of their software. Rather than allow you to use the standard binary search algorithm, company X demands you create a new version. Since recursively dividing the array into two parts is so efficient for searching, the bigwigs at company X conclude dividing the array into three parts will be even more efficient. This new "3-ary" search divides the given soiled array into.'{ equal sized sorted subarrays. It finds which subarray will contain the given value and I hen recursively searches I hat subarray. If the given value is in I he array you should return Hue. Otherwise you should return false Write up this new recursive algorithm using pseudocode. ( : For simplicity you can assume the number of elements in the given sorted array, n, is a power of 3) Create a recurrence to represent the worst case run time of our new "3-ary" search from the pseudocode. ( : The worst case run time occurs when the given value is not in the array) Use master theorem to solve you above recurrence relation. Compare this asymptotic run time to that of binary search. Does our new algorithm perform significantly better than binary search?

Explanation / Answer

(1)

(2)

The following is recursive formula for counting comparisons in worst case of Ternary Search.

(3)

The recurrence for the number of comparisons made by this ternary search is: T(n) = T(n/3) + 2. However, just as for binary search the second case of the Master Theorem applies. We therefore conclude that T(n) (log(n)).

(4)

The following is recursive formula for counting comparisons in worst case of Binary Search.

The following is recursive formula for counting comparisons in worst case of Ternary Search.

Therefore, the comparison of Ternary and Binary Searches boils down the comparison of expressions 2Log3n and Log2n . The value of 2Log3n can be written as (2 / Log23) * Log2n . Since the value of (2 / Log23) is more than one, Ternary Search does more comparisons than Binary Search in worst case.

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

---

---

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