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
I think the translation looks like Tag=29...
What significance does this line holds in this...
First of all, congratulations!