You, Alice and Bob are working on recursive search algorithms and have been studying a variant of binary search called trinary search. Alice has created the following pseudocode for this algorithm: TSearch (A[a...b], t) If a b return -1 Let pl = a + Floor ((b-a)/3) If A[p1] = t return pl If A[p1] > t return TSearch (A[a...p1-1], t) Let p2= a + Ceiling (2(ba)/3) If A[p2] = t return p2 If A[p2] > t return TSearch (A [p1+1...p2-1],t) Return TSearch (A [p2+1...b],t) EndTSearch a) State a recurrence relation that expresses the number of operations carried out by this recursive algorithm when called on an input array of size n. b) Bob has heard that trinary search is no more efficient than binary search when considering asymptotic growth. Help prove him correct by using induction to show that your recurrence relation is in (log₂ n) as well. i. Split the tight bound into and upper (big-O) and lower (big-n). ii. For each bound select a function from e(log₂ n) to use in your proof, like alog₂ n or alog₂ n-b. Remember there are typically multiple ways to prove the theorem using different choices of functions. iii. Use induction to prove your bound. Include all parts of the proof including base case, inductive hypothesis and inductive case. Be as precise as possible with your language and your math. Remember it's possible to get stuck at this point if you have selected the wrong function in the last step.
You, Alice and Bob are working on recursive search algorithms and have been studying a variant of binary search called trinary search. Alice has created the following pseudocode for this algorithm: TSearch (A[a...b], t) If a b return -1 Let pl = a + Floor ((b-a)/3) If A[p1] = t return pl If A[p1] > t return TSearch (A[a...p1-1], t) Let p2= a + Ceiling (2(ba)/3) If A[p2] = t return p2 If A[p2] > t return TSearch (A [p1+1...p2-1],t) Return TSearch (A [p2+1...b],t) EndTSearch a) State a recurrence relation that expresses the number of operations carried out by this recursive algorithm when called on an input array of size n. b) Bob has heard that trinary search is no more efficient than binary search when considering asymptotic growth. Help prove him correct by using induction to show that your recurrence relation is in (log₂ n) as well. i. Split the tight bound into and upper (big-O) and lower (big-n). ii. For each bound select a function from e(log₂ n) to use in your proof, like alog₂ n or alog₂ n-b. Remember there are typically multiple ways to prove the theorem using different choices of functions. iii. Use induction to prove your bound. Include all parts of the proof including base case, inductive hypothesis and inductive case. Be as precise as possible with your language and your math. Remember it's possible to get stuck at this point if you have selected the wrong function in the last step.
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
![**Understanding Trinary Search Algorithm**
**Introduction:**
You, Alice, and Bob are exploring various recursive search algorithms. One such algorithm is a variant of binary search called trinary search. Alice has created pseudocode for this algorithm, which we will analyze and understand.
**Trinary Search Pseudocode:**
```
TSearch(A[a...b], t)
If a > b return -1
Let p1 = a + Floor((b - a)/3)
If A[p1] = t return p1
If A[p1] > t return TSearch(A[a...p1-1],t)
Let p2 = a + Ceiling(2(b - a)/3)
If A[p2] = t return p2
If A[p2] > t return TSearch(A[p1+1...p2-1],t)
Return TSearch(A[p2+1...b],t)
EndTSearch
```
**Explanation:**
- **Line 1:** The function `TSearch` searches for the target value `t` within the array segment `A[a...b]`.
- **Line 2:** If `a` is greater than `b`, it returns -1, indicating the target is not found.
- **Line 3:** Calculate `p1`, putting it one-third of the way through the current array segment.
- **Line 4:** If the value at `p1` is equal to `t`, return the index `p1`.
- **Line 5:** If the value at `p1` is greater than `t`, recur on the left segment `A[a...p1-1]`.
- **Line 6:** Calculate `p2`, putting it two-thirds of the way through the current array segment.
- **Line 7:** If the value at `p2` is equal to `t`, return the index `p2`.
- **Line 8:** If the value at `p2` is greater than `t`, recur on the middle segment `A[p1+1...p2-1]`.
- **Line 9:** Otherwise, recur on the right segment `A[p2+1...b]`.
**Exercises:**
1. **Exercise (a):** State a recurrence relation that expresses the number of operations carried out by this recursive algorithm when called on an input array of size](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fa0c2266a-9a17-4b5f-a3a4-de1bbbae4b7e%2F11bc43e4-9ee4-4654-ad0a-fc1f903c4513%2F1xrhrdk_processed.jpeg&w=3840&q=75)
Transcribed Image Text:**Understanding Trinary Search Algorithm**
**Introduction:**
You, Alice, and Bob are exploring various recursive search algorithms. One such algorithm is a variant of binary search called trinary search. Alice has created pseudocode for this algorithm, which we will analyze and understand.
**Trinary Search Pseudocode:**
```
TSearch(A[a...b], t)
If a > b return -1
Let p1 = a + Floor((b - a)/3)
If A[p1] = t return p1
If A[p1] > t return TSearch(A[a...p1-1],t)
Let p2 = a + Ceiling(2(b - a)/3)
If A[p2] = t return p2
If A[p2] > t return TSearch(A[p1+1...p2-1],t)
Return TSearch(A[p2+1...b],t)
EndTSearch
```
**Explanation:**
- **Line 1:** The function `TSearch` searches for the target value `t` within the array segment `A[a...b]`.
- **Line 2:** If `a` is greater than `b`, it returns -1, indicating the target is not found.
- **Line 3:** Calculate `p1`, putting it one-third of the way through the current array segment.
- **Line 4:** If the value at `p1` is equal to `t`, return the index `p1`.
- **Line 5:** If the value at `p1` is greater than `t`, recur on the left segment `A[a...p1-1]`.
- **Line 6:** Calculate `p2`, putting it two-thirds of the way through the current array segment.
- **Line 7:** If the value at `p2` is equal to `t`, return the index `p2`.
- **Line 8:** If the value at `p2` is greater than `t`, recur on the middle segment `A[p1+1...p2-1]`.
- **Line 9:** Otherwise, recur on the right segment `A[p2+1...b]`.
**Exercises:**
1. **Exercise (a):** State a recurrence relation that expresses the number of operations carried out by this recursive algorithm when called on an input array of size
Expert Solution
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 2 steps
Follow-up Questions
Read through expert solutions to related follow-up questions below.
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.Recommended textbooks for you
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)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
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)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education