n binary search, we split the list in half, perform one comparison to determine
ID: 3148033 • Letter: N
Question
n binary search, we split the list in half, perform one comparison to determine if our target element is in the first or second half, and repeat on the appropriate half as necessary until only one element remains. Since there are at most log2 n halving operations, we use at most 1 log2n log2n comparisons in the worst-case Now consider ternary search instead. Here we would split the list into thirds, perform (at most) 2 comparisons to determine which third contains our target element, and repeat on the appropriate third as necessary until only one element remains i. What is the worst-case number of comparisons performed by ternary search? Explain. ii. Which algorithm performs fewer comparisons in the worst-case, and by how much? Your answer should be in the form, "Algorithm A performs r-times fewer comparisons than Algo- rithm B" for appropriate values of A, B, and x. Hint: The following mathematical fact may come in handy: it allows one to change the base of a logarithm. loga n = logb n/logba Let us now generalize to k-ary search, where we split the list into k equal size groups and perform (at most) k- 1 comparisons to determine the appropriate group on which to repeat. iii. What is the worst-case number of comparisons performed by k-ary search? Explain. iv. What is the integer value of k which minimizes the number of comparisons in the worst-case? Explain. Hint: Ensure that your expression from part i is in the form f(k) log2n for some function f(k). To do this, make use of the fact that loga n log,n/log, a, as you did above.Explanation / Answer
Hi,
as with binary search the worst case in ternary search also would happen, when the element is not present and it is smaller than all the elements
and the number of comparisons is 4 log3n comparisons
the worst case comparisons of binary search is 3 log2 n,
therefiore, ternary search is 2 / Log23 more than binary search
2. worst case in ternary search would still be the same case, and the number of comparisons would be
(k+1)logk n , now we can convert this in log base 2 as (k+1)*log2 n * logk 2
which will be minimised when k=2
Thumbs up if this was helpful, otherwise let me know in comments
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.