recategorized by
2,359 views
3 votes
3 votes
Why to prefer binary search over ternary search?Can someone give recreance relation for ternary search,so that i can compare both
recategorized by

2 Answers

7 votes
7 votes

When we are talking about better one we are minimizing the no of comparisons required  in worst case which can be best expressed by setting up recurrences and solving since these algo's are recursive in nature

For binary search :- T(n)=T(n/2)+1                   //at each stage problem is divided into half and
                                                                           one comparison for choosing the half
Solving for closed form expression for T(n) using repeated substitution with T(1)=1 as base T(n)=log2n+1

in Ternary search :- T(n)=T(n/3)+2                   //at each stage problem is reduced to 1/3rd size
                                                                           but # of comparisons at each stage is 2
and again solving closed form by repeated substitution would yield T(n)=2.log3n +!
Now if you compare these two by changing base of logs as 2.log3n=  (2 / log23) * log2n and you can verify that  (2 / log23)>1 

The same argument can be used to compare worst case # of comparisons to show that dividing in half is best possible split.

An intuitive argument for this might be that if we can repeatedly think about the decreasing log base factor and always get better results with (k+1)-ary search then k-ary search but clearly if we keep doing this and hit n-ary search then it is equivalent to doing a linear search with # of comparisons as n-1 . So at some point the overheads increase so much that the decreasing log base factor no longer helps , As by the maths above that happens for k=2

edited by
0 votes
0 votes

The recurrence relation for binary search is 

T(n) = T(n/2) + 2,  T(1) = 1

The recurrence relation for ternary search is 

 T(n) = T(n/3) + 4, T(1) = 1
Time Complexity for Binary search = 2clog2n + O(1)
Time Complexity for Ternary search = 4clog3n + O(1)

Therefore, the comparison of Ternary and Binary Searches boils down the comparison of expressions 2Log3n and Log2n . The value of 2Log3n can be written as (2 / Log23) * Log2n . Since the value of (2 / Log23) is more than one, Ternary Search does more comparisons than Binary Search in worst case.

Related questions

4 votes
4 votes
1 answer
1
Aghori asked Nov 5, 2017
1,162 views
There are two sorted list each of length $n$. An element to be searched in the both the lists. The lists are mutually exclusive. The maximum number of comparisons require...
1 votes
1 votes
4 answers
4
Abhishek Kumar 38 asked Dec 15, 2018
2,055 views
There are two sorted list each of length n. An element to be searched in the both the lists. The lists are mutually exclusive. The maximum number of comparisons required ...