Win a copy of Svelte and Sapper in Action this week in the JavaScript forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Ron McLeod
• Paul Clapham
• Bear Bibeault
• Junilu Lacar
Sheriffs:
• Jeanne Boyarsky
• Tim Cooke
• Henry Wong
Saloon Keepers:
• Tim Moores
• Stephan van Hulst
• Tim Holloway
• salvin francis
• Frits Walraven
Bartenders:
• Scott Selikoff
• Piet Souris
• Carey Brown

# running time of ternary search

Ranch Hand
Posts: 407
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?

Greenhorn
Posts: 3
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.