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.

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.

All Courses

From novice to tech pro — start learning today.

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:

http://www.ddj.com/ddj/1998/1998_04/lead/lead.htm

I hope this enough and that it'll help.

Arnon David.