Оценка сложности алгоритмов

• $O(1)$ - константная сложность
• $O(n)$ - линейная сложность. Не $O(2n)$
• $O(log n)$ - логарифмическая
• $O(n^2)$ - квадратичные
• $O(n^3)$ - P полиномиальная сложность
• $O(n^{const} + m^{const} + n*m)$ - тоже полиномиальная сложность
• $O(n log n)$ - большинство "быстрых" сортировок
• $O(2^n)$ - эспоненциальная сложность. например: перебор всех подмножеств
• $O(n^n)$

Квадратичные сортировки

src = "1 2 43 10 102 -1"
A_copy = list(map(int, src.split()))

Сортировка выбором

# Ставим минимум из i..n-1 на i-ое место
A = A_copy.copy()
n = len(A)
for i in range(n - 1):
    min_value = A[i]
    min_idx = i
    for j in range(i + 1, n):
        if A[j] < min_value:
            min_value = A[j]
            min_idx = j
    A[i], A[min_idx] = A[min_idx], A[i]

assert A == sorted(A_copy)
print(*A)

-1 1 2 10 43 102

Сортировка подсчетом