Question

Analyze the worst-case time complexity of the algorithm you devised in Exercise 33 of Section 3.1 for finding the first term of a sequence less than the immediately preceding term.

Short answer

O(n)

Step-by-step solution

Write Algorithm

Result previous exercise:

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

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

while ( $i\le nandlocation=0$)

if $a_i<a_{i-1}thenlocation:=ielsei:=i+1$

return location

Solution

In worst-case scenario, there is no term less than the immediately preceding term and thus the algorithm will then end when$i=n+1$.

The algorithm makes 3 comparisons in each iteration of the while-loop$(i\le n,location=0and{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 iterations of the while-loop.

When i = n - 1 , then there are 2 comparisonsdata-custom-editor="chemistry" $(\mathrm{i}\le \mathrm{n},\mathrm{location}=0)$.

The number of comparisons is then the product of the number of iterations and the number of comparisons per iteration, increased by the number of comparisons for the case $i=n+1$.

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

Thus at most 3n - 1 comparisons are made and$3n-1isO\left(n\right)$.