Describe the worst-case time complexity, measured in terms of comparisons, of the ternary search algorithm described in Exercise 27 of Section 3.1.
Step 2 of 3
Solution: Step1:In this problem we have to analyze the worst-case time complexity of the ternary search algorithms.In ternary search algorithm we first divide the list of given ordered number into three parts.The division is done by [1,n/3],[n/3+1,2n/3],2n/3+1,n]Step 2 :Next we find in which, the desired number must lie.So that compare the desired number with the last element of the first part. * If the desired number is small..’. Our search arrow down to the first part, whose size is of the given list.* If the desired number is greater than the last element of the second part.If desired number is smaller,than we search the second part or else the third part..’. At most two comparisons to shorten the search result by 1/3rd.
Textbook: Discrete Mathematics and Its Applications
Author: Kenneth Rosen
This textbook survival guide was created for the textbook: Discrete Mathematics and Its Applications, edition: 7. The answer to “Describe the worst-case time complexity, measured in terms of comparisons, of the ternary search algorithm described in Exercise 27 of Section 3.1.” is broken down into a number of easy to follow steps, and 22 words. Discrete Mathematics and Its Applications was written by and is associated to the ISBN: 9780073383095. This full solution covers the following key subjects: Algorithm, Case, Comparisons, complexity, describe. This expansive textbook survival guide covers 101 chapters, and 4221 solutions. The full step-by-step solution to problem: 25E from chapter: 3.3 was answered by , our top Math solution expert on 06/21/17, 07:45AM. Since the solution to 25E from 3.3 chapter was answered, more than 270 students have viewed the full step-by-step answer.