Question

Determine the worst-case complexity in terms of comparisons of the algorithm from Exercise 5 in Section 3.1 for determining all values that occur more than once in a sorted list of integers.

Short answer

O(n)

Step-by-step solution

Write Algorithm

Result previous exercise:

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

$$\begin{gathered} S:=\varphi \\ {a}_{n+1}:=a_n-1 \end{gathered}$$

for$i:=2ton$

if$a_i=a_{i-1}and{a}_i<a_{i+1}thenS:=S\cup \left\{a_i\right\}$n

return S.

Solution

The algorithm makes 2 comparisons in each iteration of the for-loop $(a_i=i-1and{a}_i<a_{i+1})$

Since i can take on the values from 2 to n, i can take on at most n - 1 values and thus there are at most n - 1 iterations of 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 2=2n-2$

Thus at most 2n - 2 comparisons are made and data-custom-editor="chemistry" $2\mathrm{n}-2\mathrm{is}\mathrm{O}\left(\mathrm{n}\right)$.