По этой логике, почему существует n (n-1) / 2 итераций для внутреннего цикла?Если сумма от 1 до N приводит к n / 2 * (n + 1), то почему сумма от 1 до N-1 не приводит к n / 2 * (n)?
Вычтите 1 из обоих вхождений n .n × (n + 1) / 2 уменьшается до (n-1) × (n + 1-1) / 2, что равно (n-1) × n / 2.Поменяйте местами два члена, и вы получите n × (n-1) /2.
Сумма целых чисел от 1 ... N = N * (N + 1) /2.
Следовательно, сумма целых чисел от 1...(N-1) = (N-1)*(N)/2, а не N/2*N, как выпретензия.
1...(N-1)
(N-1)*(N)/2
N/2*N
В любом случае, Big-O остается O(n^2).
O(n^2)