Question

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

Short answer

O(n)

Step-by-step solution

Write Algorithm

Result previous exercise:

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

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

for $i:=1ton$

$count(a_i):=1$

for $k:=2ton$

if $a_k=a_{(}k-1)\hspace{0.33em}thencount(a_k):=count(a_{k-1})+1$

if $count\left(a_k\right)>j$then

$j:=count\left(a_k\right)$

for $m:=1ton$

if $count(a_m)=j$ then role="math" localid="1668624593950" $S:=S\cup \left\{a_m\right\}$

return S.

Prove

The algorithm makes 2 comparisons in each iteration of the second for-loop of k (if $a_k=a_{k-1}andifcount\left(a_k\right)>j)$.

Since k can take on the values from role="math" localid="1668624785271" $2\mathrm{to}\mathrm{n}(\mathrm{for}\mathrm{k}:=2\mathrm{to}\mathrm{n})$, k can take on values and thus there are n - 1 iterations in the second for-loop.

The algorithm makes 1 comparison in each iteration of the third for-loop of m(if $count(a_m)=j).$).

Since m can take on the values from to n (for to n), m can take on n values and thus there are n iterations in the third for-loop.

The number of comparisons is then the sum of the product of the number of iterations and the number of comparisons per iteration for each loop (Note: We take the sum, because the two for-loops are not nested):

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

Thus $3n-2$comparisons are made and $3n-2$ is $O\left(n\right)$.