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 Insertion_Sort(A): A is a list of n integers

1 for i = 1 to n-1 do

2 x = a_i

3 j = i − 1

4 while (j $\geq$ \geq 0) do

5 if $x \geq a_j$ x \geq a_j then

6 break

7 end if

8 $a_{j+1} = a_j$ a_{j+1} = a_j

9 j = j − 1

a end while

b $a_{j+1} = x$ a_{j+1} = x

c end for

d return A

We consider comparison as the operation to be analyzed

The pseudocode contains a nested loop.

In each iteration in the inner loop, there are 2 operations.

The inner loop is a while loop for variable j and the number of iterations is i-1 in the worst case.

There are at most $2\times (1+2+\cdots+(n-1)) + 2(n-1)+1$ 2\times (1+2+\cdots+(n-1)) + 2(n-1)+1 operation.

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

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

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

Додати до Chrome