Время выполнения кода сортировки

Question

Sort(B) 
for i = 0 to (n-1) 
    x = (i+1); 
    for j = (i+2) to n 
     if B[x] > B[j] 
      x = j; 
    if x != (i+1) 
     temp = B[i+1]; 
     B[i+1] = B[x]; 
     B[x] = temp; 

Какое время работы T (n)? проблема связана с внутренним циклом (для j = (i + 2) до n) Каков наихудший сценарий для внутреннего цикла? И что лучше всего? Я думаю, что они такие же, потому что они независимы, но я хочу убедиться.

Answer 1

Время работы O (n^2).

Каждая внутренняя петля принимает O(n-i) времени, для увеличения значений i от 0 до n-1.

Это дает временную сложность:

T(n) <= CONST*(n-0 + n-1 + n-2 + ... + n-(n-1)) = 
    = CONST*(1 + 2 + ... + n) = CONST*(n(n+1)/2) 

Последнее уравнение происходит от sum of arithmetic progression.

Поскольку n (n + 1)/2 находится в O (n^2), это временная сложность.

Answer 2

Как показал другой ответ, время выполнения алгоритма равно O (n^2). Я просто хочу указать, что алгоритм выглядит не совсем корректно для меня, потому что он не сортирует первый элемент (B [0] в этом случае) массива.