# ternary search algorithm

What is the worst case time complexity in big-oh notation for a ternary search algorithm?  I think it is log base3 of N but I can't find any of my old text books to verify.  Please respond.  Thanks.
###### Who is Participating?

x

Commented:
I think you can find the proof in:
http://www.info.unicaen.fr/~clement/SODA/node3.html

if you want, there's a source code (java) for ternary search at:
http://www.coastal.edu/~mhanna/src/TernarySearchAlgorithm.java
http://www.coastal.edu/~mhanna/src/TernarySearchDAlgorithm.java

an extract from:
http://pascal.math.yorku.ca/Courses/9697/Math2320/dr2.html:

" 21 ternary search (determine divide and conquer)
(Answer is book is infinite loop, see why you need program verifications?) Plan for [a_1 < a_2 < ... < a_n] is to see if value x lies among a_1 upto (roughly) a_(n/3), or among a_(n/3 +1) up to a_(2n/3), or in the final third. Whichever is the case, essentially recursively call the algorithm to search the subinterval. l will denote index of left end of interval to search and r will be the index of right end.

Procedure Ternary( [a_1, ..., a_n]: sorted list; x: number)
l:=1, r:=n
while l < r
begin
k := floor(r+l /3)  { note k is equal l + floor(r-l /3) }
if x > a_k
then   { x is not in first third }
begin
k' := floor(2(r+l) /3)  { and k' is  l + 2* floor(r-l /3)
if x > a_k' then l:= k' +1  { since x not in first 2 thirds }
else   { x not in first or last third }
begin
l := k+1
r := k'
end
else r := k   { first third is only possibility }
end  { when this is done l = r and x = a_r or not in list }
if x = a_r then  A := 1
else  A := 0
output A

If f(n) is number of steps for searching length n, then if C is the actually number of lines of code, then f(n) is something like (in fact a little less than) f(n/3) + C. Although this is not technically a recursive algorithm it is clear that f(n) is larger than f(n/3)+C (and not significantly smaller than this). Therefore f is O(log(n)). We could put the log to be base 3 but this is the same big-O behaviour. "

also, look at:

I hope this enough and that it'll help.

Arnon David.
0

Commented:
O(log base3 of N) = O(log base2 of N)
0

Author Commented:
impressive!
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.