jay vas

Ranch Hand

Posts: 407

posted 6 years ago

Hi guys : I saw in a book that the running time of ternary search (dividing a list into 1/3 and 2/3 sized segments, rather than to equal (1/2) size segments) is

This evades me. It makes sense that for binary search, its log(base 2)^n... but im not sure why trinary search is log (base 3/2)^n.

Any ideas. hints?

This evades me. It makes sense that for binary search, its log(base 2)^n... but im not sure why trinary search is log (base 3/2)^n.

Any ideas. hints?

posted 6 years ago

No prior knowledge but can give a first-principles answer. There looks to be some confusion generally as to what ternary search is. Wikipedia http://en.wikipedia.org/wiki/Ternary_search goes for the 1/3, 2/3 definition applied to single max|min unimodal data lists. This posting http://cs-people.bu.edu/evimaria/cs131-11/ps5.pdf mentions three equal sublists but does not disclose the course literature . Have a feeling that superficially the worst case running time (asymptotic complexity) is the same for both.

First consider why running time for divide and conquer is a Log expression: List division ends up with a sublist length unity to get the result. In the worst case the number of divisions by the factor e.g. 2, 3/2, to get unity is the same as the required number of expansions by the factor applied to the unity sublist to get back to the complete list length N. For binary division we get 1 * 2 * 2 * ... = N. Definition of Log(N) is the power (i.e. number of multiplications) to which the base (expansion factor) must be raised to get N.

For ternary search (definition 1) : the division / expansion factor is 3/2 hence the worst case running time is Log3/2(N). Hope this makes sense. Could try and expand to equal thirds or if you would like the test for max / min in asymptotic data I have though of along the way please post.

First consider why running time for divide and conquer is a Log expression: List division ends up with a sublist length unity to get the result. In the worst case the number of divisions by the factor e.g. 2, 3/2, to get unity is the same as the required number of expansions by the factor applied to the unity sublist to get back to the complete list length N. For binary division we get 1 * 2 * 2 * ... = N. Definition of Log(N) is the power (i.e. number of multiplications) to which the base (expansion factor) must be raised to get N.

For ternary search (definition 1) : the division / expansion factor is 3/2 hence the worst case running time is Log3/2(N). Hope this makes sense. Could try and expand to equal thirds or if you would like the test for max / min in asymptotic data I have though of along the way please post.