Question

Describe the worst-case time complexity, measured in terms of comparisons, of the ternary search algorithm described in Exercise 27 of Section 3.1.

Short answer

O(log n)

Step-by-step solution

Write algorithm

Result previous exercise:

Procedure ternary $(a_1,a_2,...a_n:integerswithn\ge 1,x:integer)$

$\begin{array}{r}i:=1\\ j:=n\end{array}$

While i < j - 1

$\begin{array}{r}I:=\lfloor (i+j)/3\rfloor \\ u:=\lfloor 2(i+j)/3\rfloor \end{array}$

if $x\ge a_u$then data-custom-editor="chemistry" $\mathrm{i}:=\mathrm{u}+1$else

if $x\ge a_i$then

$\begin{array}{r}i=I+1\\ j=u\end{array}$

else j := l

if $x=a_i$ then $location:=i$else

if $x=a_i$then $location:=j$ else

$location:=0$

return location.

Prove

The algorithm makes comparison in each iteration of the while-loop $(i<j-1)$and makes at most 2 comparisons in the if-loop role="math" localid="1668622461697" $(x\ge a_{u}andx\ge a_{l}andx\ge a_{u}isfalse)$. Thus, in every iteration of the while-loop at most 1 + 2 = 3 comparisons are made.

The number of iterations is the number of times we divide the interval into 3 pieces, which is thus the power x of 3 such that $3^x\ge n$and thus $x=\lceil lo{g}_{3}n\rceil$.

The number of comparisons is then the product of the number of iterations and the number of comparisons per iteration:

Number of comparisons$=\lceil lo{g}_{3}n\rceil \cdot 3=3\lceil lo{g}_{3}n\rceil$

Thus, at most $3\lceil lo{g}_{3}n\rceil$comparisons are made and $3\lceil lo{g}_{3}n\rceil$ is $O(\log n)$.