Question

Analyze the worst-case time complexity of the algorithm you devised inExercise 32 of Section 3.1for finding all terms of a sequence that are greater than the sum of all previous terms.

Short answer

O(n)

Step-by-step solution

Write Algorithm

Result previous exercise:

Procedure: greater than sum $(a_1,a_2,...a_n:integerswithn\ge 1)$.

$$\begin{gathered} j:=1 \\ S:=\varphi \end{gathered}$$

for $i:=2ton$

ifdata-custom-editor="chemistry" $a_i>sum\mathit{}then\mathit{}S:=S\cup a_i$

$sum:=sum+a_i$

return S.

Solution

The algorithm makes 1 comparisons in each iteration of the for-loop (if $a_i>sum$).

Since i can take on the values from 2 to n$(fori:=2ton)$ , i can take on values and thus there are 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 1=n-1$.

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