Question

Analyze the worst-case time complexity of the algorithm you devised in Exercise 29 of Section 3.1 for locating a mode in a list of nondecreasing integers.

Short answer

O(n)

Step-by-step solution

Write Algorithm

Result previous exercise:

Procedure single mode $(a_1,a_2,...a_n:integerswithn\ge 1and{a}_1\le a_2\le ...\le a_n)$

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

for$k:=2ton$

if role="math" localid="1668624085038" $a_k=a_{k-1}\hspace{0.33em}then\hspace{0.33em}i:=1+1elsei:=1$

if i > j then

$j:=i$

$max:=a_k$

return mode.

Prove

The algorithm makes comparison in each iteration of the for-loop (if i > j ).

Since k can take on the values from 2 to n (for k := 2 to n), k can take on n - 1 iterations in the for-loop.

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

Number of comparisons$=(n-1)\cdot 1=n-1$.

Thus n - 1 comparisons are made and n - 1 is O(n) .