Consider the following algorithm called trisection search. Trisection search is an algorithm that, given a sorted list L of integers, determines whether or not a given integer x is an element of L. For convenience, let's assume that the length of Lis 3º for some integer p. Here's the algorithm: Algorithm Trisection Search(x, L): 1. If I has length 1, then return True if the single element of L is equal to x, and return False otherwise. 2. Divide L into 3 equal pieces, called L₁, L2, and L3. Let the final elements of each of these lists be l1, l2, and l3 respectively. ○ If x ≤ l₁, return TrisectionSearch(x, L₁). ○ Else, if l₁ < x ≤ l2, then return TrisectionSearch(x, L₂). o Else, if l2 < x, then return TrisectionSearch(x, L3). Part A Give a big-O estimate for the number of comparisons between integers used by trisection search on a list of length n 3º. To do so, use the following steps: = 1. Write down and justify a recurrence relation describing the number of comparisons required (Example 1 from the reading will be helpful). 2. Apply a theorem from the reading to obtain a big-O estimate. Part B For each Respond with a "true" or a "false" and a quick explanation to each of the following two statements: 1. Trisection search requires exactly as many comparisons between integers as binary search. 2. Trisection search requires no more than 10% more comparisons than binary search. 3. If n increased by a factor of 10, then the number of comparisons required by binary and trisection search would both increase by a similar (but not exactly the same) factor.
Consider the following algorithm called trisection search. Trisection search is an algorithm that, given a sorted list L of integers, determines whether or not a given integer x is an element of L. For convenience, let's assume that the length of Lis 3º for some integer p. Here's the algorithm: Algorithm Trisection Search(x, L): 1. If I has length 1, then return True if the single element of L is equal to x, and return False otherwise. 2. Divide L into 3 equal pieces, called L₁, L2, and L3. Let the final elements of each of these lists be l1, l2, and l3 respectively. ○ If x ≤ l₁, return TrisectionSearch(x, L₁). ○ Else, if l₁ < x ≤ l2, then return TrisectionSearch(x, L₂). o Else, if l2 < x, then return TrisectionSearch(x, L3). Part A Give a big-O estimate for the number of comparisons between integers used by trisection search on a list of length n 3º. To do so, use the following steps: = 1. Write down and justify a recurrence relation describing the number of comparisons required (Example 1 from the reading will be helpful). 2. Apply a theorem from the reading to obtain a big-O estimate. Part B For each Respond with a "true" or a "false" and a quick explanation to each of the following two statements: 1. Trisection search requires exactly as many comparisons between integers as binary search. 2. Trisection search requires no more than 10% more comparisons than binary search. 3. If n increased by a factor of 10, then the number of comparisons required by binary and trisection search would both increase by a similar (but not exactly the same) factor.
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
Related questions
Question
Please help me solve this problem
![Consider the following algorithm called trisection search. Trisection search is an algorithm that,
given a sorted list L of integers, determines whether or not a given integer x is an element of L. For
convenience, let's assume that the length of Lis 3º for some integer p.
Here's the algorithm:
Algorithm Trisection Search(x, L):
1. If I has length 1, then return True if the single element of L is equal to x, and return False
otherwise.
2. Divide L into 3 equal pieces, called L₁, L2, and L3. Let the final elements of each of these lists
be l1, l2, and l3 respectively.
○ If x ≤ l₁, return TrisectionSearch(x, L₁).
○ Else, if l₁ < x ≤ l2, then return TrisectionSearch(x, L₂).
o Else, if l2 < x, then return TrisectionSearch(x, L3).
Part A
Give a big-O estimate for the number of comparisons between integers used by trisection search on
a list of length n 3º. To do so, use the following steps:
=
1. Write down and justify a recurrence relation describing the number of comparisons required
(Example 1 from the reading will be helpful).
2. Apply a theorem from the reading to obtain a big-O estimate.
Part B
For each
Respond with a "true" or a "false" and a quick explanation to each of the following two statements:
1. Trisection search requires exactly as many comparisons between integers as binary search.
2. Trisection search requires no more than 10% more comparisons than binary search.
3. If n increased by a factor of 10, then the number of comparisons required by binary and
trisection search would both increase by a similar (but not exactly the same) factor.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F385eb8fb-6648-4df6-8047-4f830c46ad3b%2F8a9df8f2-6092-4ed7-b9a8-ed15cadb34e7%2Ftwlv4s_processed.png&w=3840&q=75)
Transcribed Image Text:Consider the following algorithm called trisection search. Trisection search is an algorithm that,
given a sorted list L of integers, determines whether or not a given integer x is an element of L. For
convenience, let's assume that the length of Lis 3º for some integer p.
Here's the algorithm:
Algorithm Trisection Search(x, L):
1. If I has length 1, then return True if the single element of L is equal to x, and return False
otherwise.
2. Divide L into 3 equal pieces, called L₁, L2, and L3. Let the final elements of each of these lists
be l1, l2, and l3 respectively.
○ If x ≤ l₁, return TrisectionSearch(x, L₁).
○ Else, if l₁ < x ≤ l2, then return TrisectionSearch(x, L₂).
o Else, if l2 < x, then return TrisectionSearch(x, L3).
Part A
Give a big-O estimate for the number of comparisons between integers used by trisection search on
a list of length n 3º. To do so, use the following steps:
=
1. Write down and justify a recurrence relation describing the number of comparisons required
(Example 1 from the reading will be helpful).
2. Apply a theorem from the reading to obtain a big-O estimate.
Part B
For each
Respond with a "true" or a "false" and a quick explanation to each of the following two statements:
1. Trisection search requires exactly as many comparisons between integers as binary search.
2. Trisection search requires no more than 10% more comparisons than binary search.
3. If n increased by a factor of 10, then the number of comparisons required by binary and
trisection search would both increase by a similar (but not exactly the same) factor.
Expert Solution
![](/static/compass_v2/shared-icons/check-mark.png)
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 4 steps
![Blurred answer](/static/compass_v2/solution-images/blurred-answer.jpg)
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Similar questions
Recommended textbooks for you
![Database System Concepts](https://www.bartleby.com/isbn_cover_images/9780078022159/9780078022159_smallCoverImage.jpg)
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
![Starting Out with Python (4th Edition)](https://www.bartleby.com/isbn_cover_images/9780134444321/9780134444321_smallCoverImage.gif)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
![Digital Fundamentals (11th Edition)](https://www.bartleby.com/isbn_cover_images/9780132737968/9780132737968_smallCoverImage.gif)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
![Database System Concepts](https://www.bartleby.com/isbn_cover_images/9780078022159/9780078022159_smallCoverImage.jpg)
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
![Starting Out with Python (4th Edition)](https://www.bartleby.com/isbn_cover_images/9780134444321/9780134444321_smallCoverImage.gif)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
![Digital Fundamentals (11th Edition)](https://www.bartleby.com/isbn_cover_images/9780132737968/9780132737968_smallCoverImage.gif)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
![C How to Program (8th Edition)](https://www.bartleby.com/isbn_cover_images/9780133976892/9780133976892_smallCoverImage.gif)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
![Database Systems: Design, Implementation, & Manag…](https://www.bartleby.com/isbn_cover_images/9781337627900/9781337627900_smallCoverImage.gif)
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
![Programmable Logic Controllers](https://www.bartleby.com/isbn_cover_images/9780073373843/9780073373843_smallCoverImage.gif)
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education