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 p1 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(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 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-1). ii. For each bound select a function from (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 p1 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(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 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-1). ii. For each bound select a function from (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.
C++ Programming: From Problem Analysis to Program Design
8th Edition
ISBN:9781337102087
Author:D. S. Malik
Publisher:D. S. Malik
Chapter15: Recursion
Section: Chapter Questions
Problem 6PE
Related questions
Question
Follow the instruction, split the tight bound, select a function and use induction to prove
![**Trinary Search Algorithm and Analysis**
Alice and Bob are collaborating on recursive search algorithms and have been studying a variation of binary search known as trinary search. Detailed below is the pseudocode for the trinary search algorithm developed by Alice:
### Trinary Search Algorithm 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
```
#### Problem Analysis and Tasks:
a) **Recurrence Relation for Trinary Search:**
- **Task:** State a recurrence relation that represents the number of operations performed by this recursive algorithm for an input array of size \( n \).
b) **Asymptotic Growth Comparison:**
- **Task:** Bob has suggested that trinary search is no more efficient than binary search when considering asymptotic growth. Prove Bob's assertion by using induction to show that your recurrence relation is \( \Theta(\log_3 n) \) as well.
### Steps for Proving the Recurrence Relation
i. **Splitting Upper (big-O) and Lower (big-Ω) Bounds:**
- The goal is to determine both an upper and lower bound for the trinary search's time complexity.
ii. **Selecting a Function for Each Bound:**
- Choose appropriate functions from \( \Theta(\log_3 n) \). Examples include \( a \log_3 n \) or \( a \log_2 n - b \), but ensure multiple methodologies are considered to solidify the proof.
iii. **Inductive Proof for Bounds:**
- Use induction to validate your bounds, ensuring your proof includes every necessary component (base case, inductive hypothesis, and inductive step). Clarity and precision are paramount for conveying the logic behind each step.
- Remember the application of induction must be meticulous, focusing on the chosen functions to](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F2cd8a959-e1bd-47a3-8371-c2ace33fd6bc%2F23168705-d971-42a2-9de2-665e3d5931bb%2Fkxu9078_processed.png&w=3840&q=75)
Transcribed Image Text:**Trinary Search Algorithm and Analysis**
Alice and Bob are collaborating on recursive search algorithms and have been studying a variation of binary search known as trinary search. Detailed below is the pseudocode for the trinary search algorithm developed by Alice:
### Trinary Search Algorithm 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
```
#### Problem Analysis and Tasks:
a) **Recurrence Relation for Trinary Search:**
- **Task:** State a recurrence relation that represents the number of operations performed by this recursive algorithm for an input array of size \( n \).
b) **Asymptotic Growth Comparison:**
- **Task:** Bob has suggested that trinary search is no more efficient than binary search when considering asymptotic growth. Prove Bob's assertion by using induction to show that your recurrence relation is \( \Theta(\log_3 n) \) as well.
### Steps for Proving the Recurrence Relation
i. **Splitting Upper (big-O) and Lower (big-Ω) Bounds:**
- The goal is to determine both an upper and lower bound for the trinary search's time complexity.
ii. **Selecting a Function for Each Bound:**
- Choose appropriate functions from \( \Theta(\log_3 n) \). Examples include \( a \log_3 n \) or \( a \log_2 n - b \), but ensure multiple methodologies are considered to solidify the proof.
iii. **Inductive Proof for Bounds:**
- Use induction to validate your bounds, ensuring your proof includes every necessary component (base case, inductive hypothesis, and inductive step). Clarity and precision are paramount for conveying the logic behind each step.
- Remember the application of induction must be meticulous, focusing on the chosen functions to
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 4 steps
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
C++ Programming: From Problem Analysis to Program…
Computer Science
ISBN:
9781337102087
Author:
D. S. Malik
Publisher:
Cengage Learning
C++ Programming: From Problem Analysis to Program…
Computer Science
ISBN:
9781337102087
Author:
D. S. Malik
Publisher:
Cengage Learning