Question

Analyze the worse-case time complexity of the algorithm you devised in Exercise 31 of Section 3.1 for finding the first term of a sequence of integers equal to some previous term.

Short answer

$O\left(n^2\right)$

Step-by-step solution

Write Algorithm

Result previous exercise:

Procedure first repeated $(a_1,a_2,...a_n:integerswithn\ge 1)$

$$\begin{gathered} location:=0 \\ i:=2 \end{gathered}$$

while $i\le nandlocation=0$

$j:=1$

while $j<iandlocation=0$

if $a_i=a_{j}thenlocation:=i$

else $i:=i+1$

return location.

Solution

In worst-case scenario, the match is the last number in the list and thus the while-loop will end for the last value n ofi.

The algorithm makes 2 comparisons in each iteration of the first while-loop$(i\le n,location=0)$

The algorithm makes comparisons in each iteration of the second while-loop $(j<i,location=0,a_i=a_j)$.

Since I can take on the values from 2 to n, I can take on n - 1 values and thus there are n - 1 iterations in the first while-loop.

Since j can take on the values from 1 to n - 1 , j can take on n - 1 values and thus there are n - 1 iterations in the second while-loop.

The number of comparisons is then the product of the number of iterations and the number of comparisons per iteration for each loop. (Note: We use the product, because the while-loops are nested).

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

$\begin{array}{r}=2(n-1)+3(n-1{)}^2\\ =3n^2-4n+1\end{array}$

Thus $3n^2-4n+1$ comparisons are made and $3n^2-4n+1\mathrm{is}O\left(n^2\right)$.