• Post Reply Bookmark Topic Watch Topic
  • New Topic
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 ...
  • Campbell Ritchie
  • Liutauras Vilda
  • Jeanne Boyarsky
  • Devaka Cooray
  • Paul Clapham
  • Tim Cooke
  • Knute Snortum
  • Bear Bibeault
Saloon Keepers:
  • Ron McLeod
  • Tim Moores
  • Stephan van Hulst
  • Piet Souris
  • Ganesh Patekar
  • Frits Walraven
  • Carey Brown
  • Tim Holloway

running time of ternary search

Ranch Hand
Posts: 407
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
Posts: 3
MySQL Database Tomcat Server C++
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
Consider Paul's rocket mass heater.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!