Question

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

Short answer

O(log n)

Step-by-step solution

Write Algorithm

Result previous exercise:

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

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

While i < j - 2

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

if $x\ge a_u$ then $i:=u+1$ else

if $x\ge a_m$ then

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

Else if $x\ge a_l$ then

data-custom-editor="chemistry" $\begin{array}{r}i:=I+1\\ j:=m\end{array}$

else $j:=l$

if $x=a_i$ then := i else

if $x=a_{i+1}$then := i + 1 else

if $x=a_j$ then := j else

location := 0

return location

Prove

The algorithm makes 1 comparison in each iteration of the while-loop $(i<j-2)$ and makes at most 3 comparisons in the if-loop role="math" localid="1668623747050" $(x\ge a_{u}andx\ge a_{m}andx\ge a_{u}isfalseandx\ge a_l)$ when the previous two inequalities are false. Thus, in every iteration of the while-loop at most $1+3=4$comparisons are made.

The number of iterations is the number of times we divide the interval into 4 pieces, which is thus the power x of 4 such that $4^x\ge n$ and thus $x=\lceil lo{g}_{4}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}_{4}n\rceil \cdot 4=4\lceil lo{g}_{4}n\rceil$.

Thus, at most role="math" localid="1668623693582" $4\lceil lo{g}_{4}n\rceil$comparisons are made and $4\lceil lo{g}_{4}n\rceil isO(logn)$.