Forums Register Login

running time of ternary search

+Pie Number of slices to send: Send
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?
+Pie Number of slices to send: Send
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.
The problems of the world fade way as you eat a piece of pie. This tiny ad has never known problems:
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com


reply
reply
This thread has been viewed 3613 times.
Similar Threads
Is there an easy way to remember the operatos precedence?
Big O notation
Can't Find the bug...
Collections.sort(List, Comparator)??
1000 decimal digits? how do I count them?
More...

All times above are in ranch (not your local) time.
The current ranch time is
Mar 28, 2024 04:56:47.