×
×

# Describe the worst-case time complexity, measured in terms

ISBN: 9780073383095 37

## Solution for problem 25E Chapter 3.3

Discrete Mathematics and Its Applications | 7th Edition

• Textbook Solutions
• 2901 Step-by-step solutions solved by professors and subject experts
• Get 24/7 help from StudySoup virtual teaching assistants

Discrete Mathematics and Its Applications | 7th Edition

4 5 0 346 Reviews
27
3
Problem 25E

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-by-Step Solution:
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.

Step 3 of 3

##### ISBN: 9780073383095

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.

#### Related chapters

Unlock Textbook Solution