aspose file tools*
The moose likes Programming Diversions and the fly likes running time of ternary search Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "running time of ternary search" Watch "running time of ternary search" New topic
Author

running time of ternary search

jay vas
Ranch Hand

Joined: Aug 30, 2005
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?
Martin Humby
Greenhorn

Joined: Mar 31, 2011
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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: running time of ternary search