I read the textbook, it has a chapter with the complexity of the sorting algorithm

function selection_sort(list) for current ← 1 … list.length – 1 smallest ← current for i ← current + 1 … list.length if list[i] < list[smallest] smallest ← i list.swap_items(current, smallest) 

And there the complexity of the outer loop was calculated as 2n-2

The outer loop will perform n - 1 iterations and in each of them will perform two operations (one assignment and one exchange of values), a total of 2n - 2 operations.

Then the complexity of the inner loop through the Gauss formula for the sum of the sequence

In the worst case, the if condition is always met. This means that the inner loop will perform one comparison and one assignment (n (n-1)) / 2 times, hence n ^ 2 - n operations.

And the reason for creating the topic:

In general, the cost of the 2n - n algorithm is the sum of the operations of the outer loop and n ^ 2 operations of the inner loop. We get the time complexity: n ^ 2 + n - 2

I will not say that the difficulties in the quotation above do not at all correspond to what they themselves derived, now about something else: does one really need to summarize? In each external cycle, an internal one is executed, so there must be multiplication, respectively?

  • 2
    The number of internal loop operations is already multiplied. Otherwise, there would be no n ^ 2. n^2 - n is the number of operations of the inner loop (already multiplied by the number of iterations of the outer loop), and 2n - 2 is the number of operations of the outer loop (without the inner loop). Further, we sum it up . - AnT
  • It is clear, thank you, inattentively I somehow - Vakarine

0