Crowdly

Додати до Chrome

Given the following algorithm, matching each statement to the correct sequence f...

✅ Перевірена відповідь на це питання доступна нижче. Наші рішення, перевірені спільнотою, допомагають краще зрозуміти матеріал.

Given the following algorithm, matching each statement to the correct sequence for complexity analysis.

procedure TailSums(A): A is a list of n integers

1 for i = 0 to n-2 do

2 j = i + 1

3 while (j < n) do

4 A[i] = A[i] + A[j]

5 j = j + 1

6 end while

7 end for

8 return A

In each iteration in the inner loop, there is 1 operation.

We consider comparison as the operation to be analyzed

There are (1+2+⋯+(n−1))+2(n−1)+1(1+2+\cdots+(n-1)) + 2(n-1)+1 operation.

The complexity of this algorithm is O(n2)O( n^2 )

The inner loop is a while loop for variable jj and the number of iterations is n−i−1n-i-1.

The outer loop is a for loop for variable ii and the number of iterations is n−1n-1.

The pseudocode contains a nested loop.

Отримайте необмежений доступ до відповідей на екзаменаційні питання - встановіть розширення Crowdly зараз!

Додати до Chrome